В течение трех лет математик-логик австрийского происхождения Курт Гёдель (тогда ему было двадцать пять лет, и он жил с матерью в Вене) получил на первые два из этих вопросов неожиданные ответы: «нет» и «нет». В своей «теореме о неполноте» он доказал, что существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты. Среди них, если немного упростить, оказались те, которые были сродни таким самореферентным утверждениям, как «это утверждение недоказуемо». Если утверждение верно, то в нем декларируется, что мы не можем доказать, что оно верно; если оно ложно, это также приводит к логическому противоречию. Это отчасти напоминает древнегреческий «парадокс лжеца», в котором истинность утверждения «данное утверждение ложно» не может быть определена. (Если утверждение истинно, то оно также и ложно, и наоборот.)

Приводя в качестве примера утверждения, которые не могут быть ни доказаны, ни опровергнуты, Гёдель показал, что любая формальная система, достаточно мощная, чтобы выражать обычную математику, неполна. Он также сформулировал сопутствующую теорему, которая с определенностью дала отрицательный ответ на второй вопрос Гильберта.

Оставался третий вопрос Гильберта — вопрос о разрешимости, или, как Гильберт назвал его, Entscheidungsproblem, «проблема разрешения». Несмотря на то, что Гёдель привел утверждения, которые не могут быть ни доказаны, ни опровергнуты, возможно, этот странный класс утверждений можно было бы как-то определить и изолировать, оставив остальную часть системы полной и непротиворечивой. Для этого нам потребовалось бы найти какой-то метод принятия решения о том, является ли доказуемым данное логическое утверждение. Когда великий профессор из Кембриджа математик Макс Ньюман читал Тьюрингу лекцию, в которой рассказывал о вопросах Гильберта, он сформулировал проблему Entscheidungsproblem в следующем виде: «Существует ли „механический процесс“, который можно было бы использовать для определения доказуемости данного логического утверждения»?

Тьюрингу понравилась концепция «механического процесса». Однажды летом 1935 года он, как обычно, совершал пробежку вдоль реки Или, но километра через три остановился и прилег среди яблонь в Гранчестер-Медоуз, решив обдумать этот вопрос. Он воспринял понятие «механический процесс» в буквальном смысле и попытался придумать механический процесс — воображаемую машину — и применить его к решению данной проблемы.

«Логическая вычислительная машина», которую он придумал (как мысленный эксперимент, а не как настоящую машину, которую нужно создать), была на первый взгляд довольно проста, но теоретически могла выполнять любые математические вычисления. Она состояла из бумажной ленты неограниченной длины, на которой внутри квадратиков содержались символы, в простейшем двоичном примере этими символами могли быть просто единица и пробел. Машина могла бы читать символы на ленте и выполнять определенные действия согласно заданной ей «таблице команд».

Таблица команд должна указать машине, что делать при любой конфигурации, в которой она оказалась, и в зависимости от того, какой символ, если таковые имеются, она обнаружила в соответствующем квадрате. Например, таблица команд для конкретной задачи может состоять в том, что если машина была в конфигурации 1 и увидела 1 в квадрате таблицы команд, то она должна передвинуться на одну клетку вправо и перейти в конфигурацию 2. Довольно удивительно для нас, но, видимо, не для Тьюринга, что такая машина, если ей задать надлежащую таблицу инструкций, может решать любые математические задачи независимо от того, насколько они сложны.

Как может эта воображаемая машина ответить на третий вопрос Гильберта, то есть на проблему разрешения? Тьюринг подошел к проблеме, уточнив концепцию «вычислимых чисел».