Теорема Гёделя и машины Тьюринга

В наиболее чистом виде мыслительные процессы проявля­ются в сфере математики. Если же мышление сводится к вы­полнению тех или иных вычислений, то математическое мыш­ление, по всей видимости, должно обладать этим свойством в наибольшей степени. Однако, как это ни удивительно, в действи­тельности все происходит с точностью до наоборот. Именно ма­тематика дает нам самое явное свидетельство тому, что процессы сознательного мышления включают в себя нечто, не доступное вычислению. Возможно, это покажется парадоксальным, однако для того, чтобы двигаться дальше, нам придется пока с этим парадоксом как-то примириться.

Прежде чем мы начнем, мне бы хотелось хоть как-то успо­коить читателя в отношении математических формул, которые встретятся нам в нескольких последующих разделах (§§2.2— 2.5), хотя надо признать, что страхи его не лишены оснований: ведь нам предстоит в какой-то мере уяснить для себя смысл и следствия ни много ни мало самой важной теоремы математи­ческой логики — знаменитой теоремы Курта Гёделя. Я привожу здесь очень и очень упрощенный вариант этой теоремы, опираясь, в частности, на несколько более поздние идеи Алана Тьюринга. Мы не будем пользоваться каким бы то ни было математическим формализмом, за исключением простейшей арифметики. Пред­ставленное доказательство, вероятно, будет кое-где несколько путаным, однако всего лишь путаным, а ни в коем случае не «сложным» в смысле необходимости каких-то предварительных познаний в математике. Воспринимайте доказательство в любом удобном для вас темпе и не стесняйтесь перечитывать его столько раз, сколько захочется. В дальнейшем (§§2.6—2.10) мы рассмот­рим некоторые более специфические соображения, лежащие в основе теоремы Гёделя, однако читатель, не интересующийся по­добными вопросами, может эти разделы пропустить без ущерба для понимания.

Так что же такое теорема Гёделя? В 1930 году на конферен­ции в Кенигсберге блестящий молодой математик Курт Гёдель произвел немалое впечатление на ведущих математиков и ло­гиков со всего мира, представив их вниманию теорему, которая впоследствии получила его имя. Ее довольно быстро признали в качестве фундаментального вклада в основы математики — быть может, наиболее фундаментального из всех возможных, — я же, в свою очередь, утверждаю, что своей теоремой Гёдель также положил начало важнейшему этапу развития философии разума.

Среди положений, которые со всей неоспоримостью доказал Гёдель, имеется следующее: нельзя создать такую формальную систему логически обоснованных математических правил дока­зательства, которой было бы достаточно, хотя бы в принципе, для доказательства всех истинных теорем элементарной ариф­метики. Уже и это само по себе в высшей степени удивительно, однако это еще не все. Многое говорит за то, что результаты Гёделя демонстрируют нечто большее, — а именно, доказывают, что способность человека к пониманию и постижению сути вещей невозможно свести к какому бы то ни было набору вычислитель­ных правил. Иными словами, нельзя создать такую систему пра­вил, которая оказалась бы достаточной для доказательства даже тех арифметических положений, истинность которых, в принципе, доступна для человека с его интуицией и способностью к пониманию, а это означает, что человеческие интуицию и понимание невозможно свести к какому бы то ни было набору правил. Последующие мои рассуждения отчасти имеют целью убедить читателя в том, что вышеприведенное утверждение действительно следует из теоремы Гёделя; более того, именно на теореме Гёделя основывается мое доказательство неизбежности наличия в чело­веческом мышлении составляющей, которую никогда не удастся воспроизвести с помощью компьютера (в том смысле, который мы вкладываем в этот термин сегодня).

Думаю, нет необходимости давать в рамках основного до­казательства определение «формальной системы» (если такая необходимость все же есть, то см. § 2.7). Вместо этого я восполь­зуюсь фундаментальным вкладом Тьюринга, который приблизи­тельно в 1936 году описал класс процессов, которые мы сей­час называем «вычислениями» или «алгоритмами» (аналогичные результаты были получены независимо от Тьюринга некоторыми другими математиками, среди которых следует, в первую очередь, упомянуть Черча и Поста). Такие процессы эффективно эквива­лентны процедурам, реализуемым в рамках любой математиче­ской формальной системы, поэтому для нас не имеет особого зна­чения, что именно понимается под термином «формальная систе­ма», коль скоро мы обладаем достаточно ясным представлением о том, что обозначают термины «вычисление» или «алгоритм». Впрочем и для составления такого представления математически строгое определение нам не понадобится.

Те из вас, кто читал мою предыдущую книгу «Новый разум короля» (см. НРК, глава 2), возможно, припомнят, что алгоритм там определяется как процедура, которую способна выполнить машина Тьюринга, или, если угодно, математически идеализи­рованная вычислительная машина. Такая машина функционирует в пошаговом режиме, причем каждый ее шаг полностью задается нанесенной на рабочую «ленту» меткой, которую (метку) машина «считывает» в соответствующий момент времени, и «внутренним состоянием» машины (дискретно определенным) на этот момент. Количество различных разрешенных внутренних состояний ко­нечно, общее число меток на ленте также должно быть конечным, хотя сама лента по длине не ограничена. Машина начинает рабо­ту с какого-то определенного состояния, которое мы обозначим, например, нулем «О», команды же подаются на ленте в виде, скажем, двоичного числа (т. е. последовательности нулей «0» и единиц «1»). Далее машина начинает считывать эти команды, передвигая ленту (либо, что то же самое, перемещаясь вдоль ленты) некоторым определенным образом, согласно встроенным пошаговым инструкциям, при этом действие машины на каждом этапе работы определяется ее внутренним состоянием и конкрет­ным символом, считываемым на данном этапе с ленты. Руковод­ствуясь все теми же встроенными инструкциями, машина может стирать имеющиеся метки или ставить новые. В таком духе ма­шина продолжает работать до тех пор, пока не достигнет особой команды «STOP», — именно в этот момент (и никак не раньше) машина прекращает работу, а мы можем увидеть на ленте ответ на выполнявшееся вычисление. Вот и все, можно задавать машине новую задачу.

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

Вычисления

В этом разделе мы поговорим о вычислениях. Под вычис­лением (или алгоритмом) я подразумеваю действие некоторой машины Тьюринга, или, иными словами, действие компьютера, задаваемое той или иной компьютерной программой. Не следует забывать и о том, что понятие вычисления включает в себя не только выполнение обычных арифметических действий — таких, например, как сложение или умножение чисел, — но и некоторые другие процессы. Так, частью вычислительной процедуры могут стать и вполне определенные логические операции. В качестве примера вычисления можно рассмотреть следующую задачу:

(А) Найти число, не являющееся суммой квадратов трех чисел.

Под «числом» в данном случае я подразумеваю «натуральное число», т. е. число из ряда

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ....

Под квадратом числа понимается результат умножения натурального числа на само себя, т. е. число из ряда

0, 1, 4, 9, 16, 25, 36, ...;

представленные в этом ряду числа получены следующим обра­зом:

0 х 0 = 0², 1 х 1 = 1², 2 х 2 = 2², 3 х 3 = 3², 4 х 4 = 4², 5х5 = 5², 6 х 6 = 6²,....

Такие числа называются «квадратами», поскольку их можно представить в виде квадратных матриц (пустой матрицей в начале строки обозначен 0):

* *, *, * *

* * * * * * , * * *

* * * * * * * *, * * * * * * * * * * * *

С учетом вышесказанного решение задачи (А) может проис­ходить следующим образом. Мы поочередно проверяем каждое натуральное число, начиная с 0, на предмет того, не является ли оно суммой трех квадратов. При этом, разумеется, рассмат­риваются только те квадраты, величина которых не превышает самого числа. Таким образом, для каждого натурального числа необходимо проверить некоторое конечное количество квадра­тов. Отыскав тройку квадратов, составляющих в сумме данное число, переходим к следующему натуральному числу и снова ищем среди квадратов (не превышающих по величине рассматри­ваемое число) такие три, которые дают в сумме это самое число. Вычисление завершается лишь тогда, когда мы находим нату­ральное число, которое невозможно получить путем сложения любых трех квадратов. Попробуем применить описанную проце­дуру на практике и начнем наше вычисление с нуля. Ноль ра­вен 0² + 0² + 0², что, безусловно, является суммой трех квадратов. Далее рассматриваем единицу и находим, что она не равна О² + + О² + О², однако равна О² + О² + I². Переходим к числу 2 и выясняем, что оно не равно ни 0² + 0² + 0², ни 0² + 0² + 1², но равно0² + 1² + 1². Затем следует число 3 и сумма 3 = 1² + 1² + 1²; далее — число 4 и сумма 4 = 0² + 0² + 2²; после 5 = 0² + 1² + 2² и 6 = 1²+1²+2² переходим к 7, и тут обнаруживается, что ни одна из троек квадратов (всех возможных троек квадратов, каждый из которых не превышает 7)

0²+0²+0² 0²+0²+1² 0²+0²+2² 0²+1²+1² 0²+1²+2²

0²+2²+2² 1²+1²+1² 1²+1²+2² 1²+2²+1² 2²+2²+2²

не дает в сумме 7. На этом этапе вычисление завершается, а мы делаем вывод: 7 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.