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

 

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

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

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

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

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

Те из вас, кто читал мою предыдущую книгу «Новый разум короля » (см. НРК, глава 2), возможно, припомнят, что алгоритм там определяется как процедура, которую способна выполнить машина Тьюринга, или, если угодно, математически идеализированная вычислительная машина. Такая машина функционирует в пошаговом режиме, причем каждый ее шаг полностью задается нанесенной на рабочую «ленту» меткой, которую (метку) машина «считывает» в соответствующий момент времени, и «внутренним состоянием» машины (дискретно определенным) на этот момент. Количество различных разрешенных внутренних состояний конечно, общее число меток на ленте также должно быть конечным, хотя сама лента по длине не ограничена. Машина начинает работу с какого-то определенного состояния, которое мы обозначим, например, нулем «0», команды же подаются на ленте в виде, скажем, двоичного числа (т.е. последовательности нулей «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 = 02, 1 × 1 = 12, 2 × 2 = 22, 3 × 3 = 32, 4 × 4 = 42, 5 × 5 = 52, 6 × 6 = 62, ….

 

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

 

 

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

 

02 + 02 + 02 02 + 02 + 12 02 + 02 + 22 02 + 12 + 12 02 + 12 + 22

02 + 22 + 22 12 + 12 + 12 12 + 12 + 22 12 + 22 + 12 22 + 22 + 22

 

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

 

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться: