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

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

Прежде чем мы начнем, мне бы хотелось хоть как-то успо­коить читателя в отношении математических формул, которые встретятся нам в нескольких последующих разделах (§§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 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.

Незавершающиеся вычисления

Будем считать, что с задачей (А) нам просто повезло. По­пробуем решить еще одну:

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

На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне воз­можно: 7 = 1² + 1² + 1² + 2², поэтому мы переходим к числу 8 (сумма 8 = 0² + 0² + 2² + 2²), далее — 9 (сумма 9 = 0² + 0² + 0² + З²) и 10 (10 = 0² + 0² + 1² + 3²) и т.д. Вычисления все продолжаются и продолжаются (. . . 23 = 1² + 2² + 3² + 3², 24 = 0² + 2² + 2² + 4², . . . , 359 = 1² + 3² + 5² + 18², . . .) и завершаться, похоже, не собираются. Мы предполагаем, что искомое число, должно быть, невообразимо велико, и для его вы­числения нашему компьютеру потребуется чрезвычайно большой промежуток времени и огромный объем памяти. Более того, мы уже начинаем сомневаться, существует ли оно вообще, это самое число. Вычисления все продолжаются и продолжаются, и конца им не видно. Вообще говоря, так оно и есть: описанная вычисли­тельная процедура завершиться в принципе не может. Известна теорема, впервые доказанная в 1770 году великим французским (и отчасти итальянским) математиком Жозефом Луи Лагранжем, согласно которой в виде суммы квадратов четырех чисел можно представить любое число. Теорема эта, кстати, весьма непро­ста (доказать ее как-то пытался великий современник Лагранжа, швейцарский математик Леонард Эйлер, человек, отличавший­ся удивительной математической интуицией, оригинальностью и продуктивностью, однако его постигла неудача).

Я, разумеется, не собираюсь докучать читателю подробно­стями доказательства Лагранжа, вместо этого рассмотрим одну не в пример более простую задачу:

(C) Найти нечетное число, являющееся суммой двух четных чи­сел.

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

0,2,4,6,8,10,12,14,16,...,

всегда получаются четные же числа; иными словами, никакая пара четных чисел не может дать в сумме нечетное число, т. е. число вида

1,3,5,7,9, 11, 13, 15,17,....

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

(D) Найти четное число, большее 2, не являющееся суммой двух простых чисел.

Вспомним, что простым называется натуральное число (отличное от 0 и 1), которое делится без остатка лишь само на себя и на единицу; иными словами, простые числа составляют следующий ряд:

2, 3, 5, 7, 11, 13, 17, 19, 23, ....

Существует довольно высокая вероятность того, что отыскание решения задачи (D) также потребует незавершающейся вычис­лительной процедуры, однако полной уверенности пока нет. Для получения такой уверенности необходимо прежде доказать ис­тинность знаменитой «гипотезы Гольдбаха», выдвинутой Гольд­бахом в письме к Эйлеру еще в 1742 году и до сих пор недоказан­ной.