Широкой публике гениальный математик Алан Тьюринг (Alan Turing) известен, вероятно, как человек, разгадавший шифр «Энигмы»>21. Благодаря чему цивилизованный мир победил нацистов. Если даже это и правда, то не вся. Главная заслуга Алана Тьюринга перед человечеством состоит в другом. В своих работах он описал то, что сегодня мы называем компьютером.
В год, когда Ральф Хартли предложил свою формулу для вычисления меры информации, великий математик Давид Гильберт (David Hilbert) сформулировал проблему разрешения (Entscheidungsproblem). Её суть сводится к тому, что у любой задачи (которую можно выразить с помощью букв или цифр) должен существовать алгоритм (порядок шагов для её решения). Если алгоритма нет (никто не может придумать), то задача не является разрешимой. Однако это не означает, что задача не может быть решена в принципе>11.
Поясним сказанное на примере. Возьмём два числа: 25 и 100. Каков их наибольший общий делитель? Пойдём не интуитивно, а строго математически. От большего числа будем отнимать меньшее. В результате трёх последовательных вычитаний получим число, которое соответствует наименьшему числу, выбранному изначально (25). Тогда можно сказать, что наибольший общий делитель для 100 и 25 есть число 25. Или: 25 – наибольшая общая мера выбранных чисел. Принято говорить, что 100 и 25 – соизмеримые величины.
Приведённый порядок вычисления – известный ещё со времен Евклида (Euclid) алгоритм для поиска наибольшего общего делителя. Но что, если существуют задачи, для которых алгоритм указать нельзя?
Вообразим два других числа. Очень больших. Длиною в миллиарды миллиардов знаков. Попробуем найти их наибольший общий делитель. (Представляю, как вы чертыхаетесь).
Ну, хорошо – предоставим это компьютеру. Пусть попотеет. Сможет ли он выполнить порученную работу? Допустим, что сможет. Возникает вопрос: сколько времени это займёт? Ответ: неизвестно.
Это так называемая «проблема остановки». Мы не знаем, как долго будет работать вычислитель (человек или машина) над решением некоторых (математически сложных) проблем. Другими словами, мы не можем для них предложить алгоритм – порядок шагов, которые нужно предпринять, чтобы получить точный ответ.
В 1931 году математик Курт Гёдель (Kurt Gödel) доказал, что во всякой сложной (с т. зр. логики и математики) умозрительной системе есть недоказуемые утверждения