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