(или опровергнуто) с помощью правил только одной этой системы? (2) Является ли этот набор непротиворечивым (и значит, никакое утверждение не может быть признано одновременно и верным и ложным)? (з) Существует ли какая-то процедура, с помощью которой можно определить, является ли данное конкретное утверждение доказуемым, или остается возможность того, что некоторым утверждениям (к таким, например, относятся математические загадки, такие как последняя теорема Ферма, гипотеза Гольдбаха или гипотеза Коллатца) суждено оставаться неразрешенными? Гильберт думал, что ответы на первые два вопроса должны быть положительными, а третий считал схоластическим. Он сформулировал это просто: “Нет такого понятия, как неразрешимая задача”.
В течение трех лет математик-логик австрийского происхождения Курт Гёдель (тогда ему было двадцать пять лет, и он жил с матерью в Вене) получил на первые два из этих вопросов неожиданные ответы: “нет” и “нет”. В своей “теореме о неполноте” он доказал, что существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты. Среди них, если немного упростить, оказались те, которые были сродни таким самореферентным утверждениям, как “это утверждение недоказуемо”. Если утверждение верно, то в нем декларируется, что мы не можем доказать, что оно верно; если оно ложно, это также приводит к логическому противоречию. Это отчасти напоминает древнегреческий “парадокс лжеца”, в котором истинность утверждения “данное утверждение ложно” не может быть определена. (Если утверждение истинно, то оно также и ложно, и наоборот.)
Приводя в качестве примера утверждения, которые не могут быть ни доказаны, ни опровергнуты, Гёдель показал, что любая формальная система, достаточно мощная, чтобы выражать обычную математику, неполна. Он также сформулировал сопутствующую теорему, которая с определенностью дала отрицательный ответ на второй вопрос Гильберта.
Оставался третий вопрос Гильберта – вопрос о разрешимости, или, как Гильберт назвал его, Entscheidungsproblem, “проблема разрешения”. Несмотря на то, что Гёдель привел утверждения, которые не могут быть ни доказаны, ни опровергнуты, возможно, этот странный класс утверждений можно было бы как-то определить и изолировать, оставив остальную часть системы полной и непротиворечивой. Для этого нам потребовалось бы найти какой-то метод принятия решения о том, является ли доказуемым данное логическое утверждение. Когда великий профессор из Кембриджа математик Макс Ньюман читал Тьюрингу лекцию, в которой рассказывал о вопросах Гильберта, он сформулировал проблему Entscheidungsproblem в следующем виде: “Существует ли «механический процесс», который можно было бы использовать для определения доказуемости данного логического утверждения”?
Тьюрингу понравилась концепция “механического процесса”. Однажды летом 1935 года он, как обычно, совершал пробежку вдоль реки Или, но километра через три остановился и прилег среди яблонь в Гранчестер-Медоуз, решив обдумать этот вопрос. Он воспринял
