Том. 22. Сон разума. Математическая логика и ее парадоксы - Хавьер Фресан

Каждая машина Тьюринга вычисляет значение единственной функции, поэтому утверждать, что все функции являются вычислимыми, можно, лишь доказав, что существует по меньшей мере столько же машин, сколько и функций, значения которых мы хотим вычислить. Однако Тьюринг установил, что бесконечное множество его машин намного меньше. Чтобы показать, что множество функций не является счетным, сначала следовало записать их в виде последовательностей из нулей и единиц. Мы можем записать в виде символов любую машину Тьюринга, поскольку она представляет собой конечную последовательность инструкций, и каждую из них можно записать несколькими символами. Как вы уже увидели, (#1,1, L, #3) означает то же, что и «Инструкция номер 1: если считан символ 1, сместиться влево и перейти к третьей инструкции». Представив машину Тьюринга как последовательность инструкций, читатель сможет найти способ, позволяющий записать все возможные машины Тьюринга в виде списка.

Больший интерес для нас будет иметь процесс «гёделизации», рассмотренный в главе 4. Он заключается в присвоении огромных натуральных чисел каждой формуле логики первого порядка так, что по известному числу можно восстановить исходную формулу. Этот метод, примененный к машинам Тьюринга, позволяет свести всю информацию, содержащуюся в программе, к одному числу. Как и в случае с «гёделизацией», машины Тьюринга соответствуют не всем числам, а только тем, которые обладают определенными свойствами. Хотя существует бесконечное множество машин Тьюринга, его размеры не могут превышать размеры множества натуральных чисел, так как всякая машина Тьюринга кодируется с помощью натуральных чисел.

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

Лейбниц, а в начале XX века и Давид Гильберт — мечтали создать машину, способную отличать истинные высказывания от ложных. Как мы отметили в главе 3, программа Гильберта по «очистке» математики от парадоксов заключалась не только в формировании ее устойчивого фундамента — с этим справились древние начиная с Евклида, и пока что основы математики стояли прочно. Для абсолютной уверенности в том, что в будущем никакой Рассел не вытащит из рукава новый парадокс, помимо укрепления логической структуры математики, требовалось рассчитать метаматематические структуры, чтобы доказать, что они способны выдержать вес всего здания науки. Первые два вопроса, которыми задался Гильберт, звучали так: является ли математика полной и непротиворечивой, иными словами, совпадает ли истинное и доказуемое, и нет ли риска столкнуться с противоречиями в математике. За три года до того, как Гёдель доказал, что для арифметики эти требования несовместимы, Давид Гильберт и его ученик Вильгельм Аккерман (1896–1962) добавили к этим вопросам еще один, который был изложен на первом пленарном заседании Международного математического конгресса в 1928 году.

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

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

Это было рискованно: наиболее вероятно, что ответом на вопрос стал бы получасовой монолог, во время которого энтузиазм говорящего рос так же быстро, как угасал интерес слушателя. Однако в этот раз математик решил, что журналист не поймет его объяснений, поэтому ограничился тем, что сказал: «Смотрите: у меня есть машина, в которую я ввожу высказывание, и она отвечает, истинно это высказывание или ложно». Тогда мнимый журналист, который до того момента прекрасно скрывал свое истинное лицо, воскликнул: «Превосходно! Не сможете ли вы как-нибудь одолжить мне эту машину на денек-другой? Я работаю со множеством математических гипотез и совершенно не представляю, истинны они или ложны».

Да, всем нам хотелось бы иметь такую машину, однако Алан Тьюринг в ходе исследований, посвященных вычислимым функциям, доказал, что создать ее невозможно. Для этого он рассмотрел универсальную машину, входными значениями для которой могли выступать не только числа, но и инструкции произвольной машины Тьюринга. Если инструкции описывали то, что мы сегодня называем программой, то универсальная машина сама по себе была подобна компьютеру и была способна имитировать, по крайней мере теоретически, работу произвольной машины Тьюринга. Описав этот абстрактный компьютер, ученый на несколько лет предвосхитил архитектуру современных компьютеров, поэтому редакция журнала Time совершенно справедливо включила его в число людей тысячелетия с комментарием: «Каждый раз, когда мы нажимаем на клавишу компьютера, мы работаем с реинкарнацией машины Тьюринга». Использовав этот компьютер (которых, строго говоря, тогда еще не существовало), Тьюринг показал, что существование подобной «машины истинности» приводит к абсурдному результату.

Посмотрим, как Тьюринг справился с проблемой разрешения. Сначала он предположил, что мечту Гильберта можно воплотить в реальность, то есть существует механический метод, позволяющий за конечное время определить, является данное высказывание истинным или ложным. В частности, этот алгоритм позволяет оценить истинность высказывания «Машина Тьюринга Т останавливается, когда на ее вход подается значение n». Как мы уже указывали, благодаря методу «гёделизации» мы можем сопоставить каждой машине Тьюринга число так, что в нем будет закодирована вся структура машины. Если n — число, описывающее некую машину Тьюринга, мы будем обозначать эту машину как Т(n). В этой нотации проблема, которую мы хотим решить, может быть записана так: остановится ли машина Тьюринга Т(n), если на ее вход подать число m? Следует подчеркнуть, что если идеальная машина, которую представлял себе Гильберт, существует, то она сможет дать ответ на этот вопрос не в каких-то конкретных случаях, а для любых значений m и n.

Следовательно, речь идет о функции двух переменных, которая для данной пары чисел (m, n) определяет, остановится ли машина Тьюринга, описываемая числом n, когда ей на вход будет подана лента, на которой будет записано число m. Вернемся к примеру с числом π и обозначим за f число машины Тьюринга, которая просматривает десятичные знаки π в поиске требуемой последовательности. При вводе параметров (9, f) наша функция вернет значение 1, если среди знаков π обнаружится последовательность из девяти девяток подряд (так как в этом случае машина остановится), в противном случае — 0 (в этом случае машина будет продолжать работу бесконечно).

Если мы предположим, что существует машина Тьюринга Р, решающая эту проблему, мы получим противоречие. Чтобы убедиться в этом, повторим еще раз принцип действия Р: это машина Тьюринга, на вход которой подаются пары чисел (m, n) и выходным значением которой может быть одно из двух значений: 1, если машина Тьюринга Т(n) при заданном исходном значении m в определенный момент остановится, и 0 — в противном случае. Иными словами, либо не существует машины Тьюринга, обозначаемой числом n (так как не все натуральные числа обозначают какую-либо машину Тьюринга), или же она существует, но программа выполняется бесконечно долго при введенном параметре m. Такая программа, представляющая собой настоящий кошмар для специалистов по информатике, называется бесконечным циклом. Здесь важно, что если бы в нашем распоряжении находилась такая машина Т, мы с легкостью смогли бы создать другую машину Тьюринга (обозначим ее через С), входным значением которой было бы одно число m и которая действовала бы следующим образом:

— если машина Тьюринга Т(n) останавливается, когда ее входное значение равно n (иными словами, если Р(n, n) равно 1), то С не остановится никогда;