В течение трех лет математик-логик австрийского происхождения Курт Гёдель (тогда ему было двадцать пять лет, и он жил с матерью в Вене) получил на первые два из этих вопросов неожиданные ответы: «нет» и «нет». В своей «теореме о неполноте» он доказал, что существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты. Среди них, если немного упростить, оказались те, которые были сродни таким самореферентным утверждениям, как «это утверждение недоказуемо». Если утверждение верно, то в нем декларируется, что мы не можем доказать, что оно верно; если оно ложно, это также приводит к логическому противоречию. Это отчасти напоминает древнегреческий «парадокс лжеца», в котором истинность утверждения «данное утверждение ложно» не может быть определена. (Если утверждение истинно, то оно также и ложно, и наоборот.)
Приводя в качестве примера утверждения, которые не могут быть ни доказаны, ни опровергнуты, Гёдель показал, что любая формальная система, достаточно мощная, чтобы выражать обычную математику, неполна. Он также сформулировал сопутствующую теорему, которая с определенностью дала отрицательный ответ на второй вопрос Гильберта.
Оставался третий вопрос Гильберта — вопрос о разрешимости, или, как Гильберт назвал его, Entscheidungsproblem, «проблема разрешения». Несмотря на то, что Гёдель привел утверждения, которые не могут быть ни доказаны, ни опровергнуты, возможно, этот странный класс утверждений можно было бы как-то определить и изолировать, оставив остальную часть системы полной и непротиворечивой. Для этого нам потребовалось бы найти какой-то метод принятия решения о том, является ли доказуемым данное логическое утверждение. Когда великий профессор из Кембриджа математик Макс Ньюман читал Тьюрингу лекцию, в которой рассказывал о вопросах Гильберта, он сформулировал проблему Entscheidungsproblem в следующем виде: «Существует ли „механический процесс“, который можно было бы использовать для определения доказуемости данного логического утверждения»?
Тьюрингу понравилась концепция «механического процесса». Однажды летом 1935 года он, как обычно, совершал пробежку вдоль реки Или, но километра через три остановился и прилег среди яблонь в Гранчестер-Медоуз, решив обдумать этот вопрос. Он воспринял понятие «механический процесс» в буквальном смысле и попытался придумать механический процесс — воображаемую машину — и применить его к решению данной проблемы[70].
«Логическая вычислительная машина», которую он придумал (как мысленный эксперимент, а не как настоящую машину, которую нужно создать), была на первый взгляд довольно проста, но теоретически могла выполнять любые математические вычисления. Она состояла из бумажной ленты неограниченной длины, на которой внутри квадратиков содержались символы, в простейшем двоичном примере этими символами могли быть просто единица и пробел. Машина могла бы читать символы на ленте и выполнять определенные действия согласно заданной ей «таблице команд»[71].
Таблица команд должна указать машине, что делать при любой конфигурации, в которой она оказалась, и в зависимости от того, какой символ, если таковые имеются, она обнаружила в соответствующем квадрате. Например, таблица команд для конкретной задачи может состоять в том, что если машина была в конфигурации 1 и увидела 1 в квадрате таблицы команд, то она должна передвинуться на одну клетку вправо и перейти в конфигурацию 2. Довольно удивительно для нас, но, видимо, не для Тьюринга, что такая машина, если ей задать надлежащую таблицу инструкций, может решать любые математические задачи независимо от того, насколько они сложны.
Как может эта воображаемая машина ответить на третий вопрос Гильберта, то есть на проблему разрешения? Тьюринг подошел к проблеме, уточнив концепцию «вычислимых чисел». Любое действительное число, которое определено с помощью математического правила, можно найти с помощью логической вычислительной машины. Даже иррациональное число, напримерр, можно вычислять с бесконечной точностью, используя конечную таблицу команд. Таким же образом можно рассчитать логарифм 7, квадратный корень из 2, или последовательность чисел Бернулли (в составленим алгоритма вычисления которых участвовала Ада Лавлейс), или любое другое число или ряд, независимо от того, насколько сложно их вычислять, лишь бы эти вычисления задавались конечным числом правил. Все они были в терминологии Тьюринга «вычислимыми числами».
Тьюринг продвинулся дальше и показал, что невычислимые числа также существуют. Это было связано с проблемой, которую он назвал «проблемой остановки». Как он показал, никаким методом заранее нельзя определить, приведет ли любая заданная таблица инструкций в сочетании с любым заданным набором исходных данных к тому, что машина найдет ответ, или же она войдет в вычисление некоторых циклов и будет продолжать пыхтеть бесконечно долго, так и не получив ответа. Неразрешимость проблемы остановки, как он показал, означает, что нет решения и у Entscheidungsproblem — проблемы разрешения Гильберта. Несмотря на надежды Гильберта, оказалось, что никакая механическая процедура не может определить доказуемость каждого математического утверждения. Теория Гёделя о неполноте, неопределенность квантовой механики и ответ Тьюринга на третий вопрос Гильберта — все они наносили удары по механической, детерминистской и предсказуемой Вселенной.
Статья Тьюринга была опубликована в 1937 году под не очень выразительным названием «О вычислимых числах и их приложении к Entscheidungsproblem». Его ответ на третий вопрос Гильберта оказался полезным для развития теории математики. Но гораздо более важным стал «побочный продукт» доказательства Тьюринга — его концепция логической вычислительной машины, которая вскоре стала известна как «машина Тьюринга». В статье он утверждал: «Можно изобрести единую машину, которую можно использовать для вычисления любого вычислимого ряда»[72]. Такая машина была бы способна выполнить команды, данные любой другой машине, и решить любые задачи, которые та машина может решить. В сущности, она была воплощением мечты Чарльза Бэббиджа и Ады Лавлейс об универсальной машине самого общего назначения.
Другое и менее красивое решение для Entscheidungsproblem с более громоздким названием «Бестиповое лямбда-исчисление» раньше в этом же году опубликовал Алонзо Чёрч, математик из Принстона. Руководитель Тьюринга — профессор Макс Ньюман — решил, что Тьюрингу было бы полезно поучиться у Чёрча. В своем рекомендательном письме Ньюман описал огромный потенциал Тьюринга. Он также добавил более личную рекомендацию, основанную на особенностях характера Тьюринга. «Он работал без всякого руководства или обсуждения с кем-либо, — написал Ньюман, — и поэтому важно, чтобы он как можно скорее вступил в контакт с ведущими специалистами в этой области, чтобы не превратился в закоренелого отшельника»[73].
