Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

• Название: ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда
• Автор: Даглас Хофштадтер
• Издательство: Издательский Дом «Бахрах-М», 2001.
• Жанр: Математика
• Год: 2001
• ISBN: ISBN 5-94648-001-4

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

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

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

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

Переведенная на 17 языков, книга потрясла мировое интеллектуальное сообщество и сразу стала бестселлером. Теперь и русский читатель получил доступ к одной из культовых книг XX века.

---

.                                                                    236,123,123,262,163,323

теперь заменим заменим свободные переменные на символ числа 4                      

~Ea:Ea':SSSS0=(SSa*SSa')                                  223,333,262,636,333,262,163,636,

.                                                                   123,123,123,123,666,111,362,123,

.                                                                   123,262,236,123,123,262,163,323,

В правой колонке происходит изоморфный арифметический процесс, в котором один большой номер превращается в другой, еще больший номер. Функцию, которая производит этот новый номер из старого, несложно описать арифметически в терминах сложения, умножения, возведения в десятую степень и так далее — но нам это не нужно. Важно здесь то, что отношения между (1) первоначальным Гёделевым номером, (2) номером, чей символ мы вставили и (3) Гёделевым номером, при этом получающимся — это примитивно рекурсивные отношения. Это значит, что на Блупе может быть написана программа-тест, которая, если мы введем в нее эти три номера, сможет ответить ДА. если между ними существуют такие отношения, и НЕТ — в противном случае. Вы можете проверить себя на способность проводить такие тесты (и в то же время убедиться, что в этом процессе нет спрятанных открытых петель), проверив следующие два случая:

(1) 362,262,112,262,163,323,111,123,123,123,123,666;

.     2;

.    362,123,123,666,112,123,123,666,323,111,123,123,123,123,666.

(2) 223,362,262,236,262,323,111,262,163;

.     1;

.     223,362,123,666,236,123,666,323,111,262,163.                            

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

   ZAM{a, a', a"}

Поскольку эта формула представляет отношения замены, нижеследующая формула ТТЧ должна являться теоремой:

ZAM{SSSSS..... SSSSS0/a, SS0/a', SSSSSS..... SSSS0/a"}

.           |________|                          |________|

.         262,111,262-«S»          123,123,666,111,123,123,666 «S»

(Это основано на первом примере отношений замены, показанном ранее в виде параллельных колонок.) С другой стороны, поскольку формула ZAM представляет собой отношения замены, формула, данная ниже, не является теоремой ТТЧ:

ZAM{SSS0/a, SS0/a', S0/a"}

Арифмоквайнирование

Пора соединить все эти части в одно гармоничное целое. Мы попробуем использовать технику ПАР-ДОКАЗАТЕЛЬСТВА-ТТЧ и формул ZAM для построения суждения ТТЧ, интерпретирующегося как «Эта строчка ТТЧ — не теорема ТТЧ». Как это возможно? Даже теперь, когда у нас есть все необходимые инструменты, ответ на этот вопрос найти нелегко.

Интересный и на вид довольно несерьезный прием состоит в подстановке в формулу ее собственного Гёделева номера. Это весьма похоже на другое, тоже легкомысленное на вид понятие «квайнирования», о котором вы прочли в «Арии в ключе G». Однако квайнирование оказалось важным, поскольку оно представляет из себя новый способ создания автореферентных суждений. Автореферентность подобного типа сначала кажется весьма странной, но, поняв ее принцип, вы найдете ее простой и изящной. Арифметическая версия квайнирования — назовем ее арифмоквайнированием — позволит нам получать суждения ТТЧ, «говорящие о себе самих».

Давайте рассмотрим пример арифмоквайнирования. Нам нужна формула, по меньшей мере, с одной переменной. Для этого годится следующая формула:

a=S0

Гёделев номер этой формулы — 262,111,123,666; теперь мы подставим этот номер в саму формулу — или, точнее, мы подставим в нее символ этого номера. У нас получится:

SSSSS.....SSSSSO=S0

|____________|

262,111,123,666 «S»

Эта новая формула очень глупа: она утверждает, что 262,111,123,666 равняется 1. Если бы мы начали со строчки ~a=S0, и затем арифмоквайнировали ее, у нас получилось бы верное высказывание, в чем вы сами можете убедиться.

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

ZAM{a'',a'',a'}

где две первые переменные совпадают. Это происходит потому, что мы используем один и тот же номер двумя разными способами (эхо Канторовского диагонального метода!) Номер а' является одновременно (1) первоначальным Гёделевым номером и (2) номером-заменой. Давайте сократим вышеприведенную формулу:

ARITHMOQUINE{a'', a'}

В переводе на русский это означает, что:

а' — Гёделев номер формулы, полученной арифмоквайнированием формулы с Гёделевым номером а''.

Предыдущее предложение — длинное и запутанное. Давайте попробуем выразить то же самое с помощью краткого и элегантного термина:

а' — арифмоквайнификация а''

Например, арифмоквайнификацией формулы 262,111,123,666 был бы следующий невероятный гигант:

123,123,123, ...... 123,123,123,666,111,123,666

|_________________________|

«123» повторяется 262, 111, 123,666 раз.

(Это всего-навсего Гёделев номер формулы, полученной, когда мы арифмоквайнировали a=S0.) Как видите, мы можем довольно легко говорить об арифмокваинировании в ТТЧ.

Последняя соломинка

Если вы снова перелистаете «Арию в ключе G», то увидите, что последний трюк, необходимый для получения автореференции по Квайну, заключается в том, чтобы квайнировать высказывание, само говорящее о квайнировании. Одного квайнирования оказывается недостаточно — вы должны квайнировать предложение о квайнировании! Нам придется использовать параллельный трюк и арифмоквайнировать формулу, саму упоминающую квайнирование. Давайте запишем эту формулу; назовем ее дядей G.

~Eа:Eа':<ПАРА-ДОКАЗАТЕЛЬСТВА-

TTЧ{a,a'}Λ ARITHMOQUINE{a",a'}>

Легко увидеть, насколько здесь замешано арифмоквайнирование. У этого «дяди», разумеется, есть Гёделев номер — мы будем называть его d. Начало и конец d и даже кое-какие фрагменты его середины мы можем прочитать без труда:

d = 223,333,262,636,333,262,163,636,212..... 161,.... 213

Для остального нам только нужно знать, как выглядят в записи формулы ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ и ARITHMOQUINE. Приводить здесь эту запись слишком сложно, да и не нужно.

Теперь осталась самая малость — нужно арифмоквайнировать самого дядю! Для этого надо избавиться от свободных переменных, которых у нас только одна — а'' — и заменить их на символ числа d. Мы получим:

~Ea:Ea':<ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{a,a'}

ΛARITHMOQUINE{SS…SSS0/a'',a'}>

.                       |___|

.                       d «S» 

Именно это и есть Гёделева строчка, которую мы называем «G». Теперь у нас возникают два вопроса, на которые необходимо ответить без промедления. Вот они:

(1) Каков Гёделев номер G?

(2) Какова интерпретация G?

Сначала ответим на первый вопрос. Как мы получили G? Мы начали с дяди и арифмоквайнировали его, так что, по определению арифмоквайнирования, Гёделев номер G — это:

арифмоквайнификация d.

Теперь второй вопрос. Постараемся перевести G на русский постепенно, шаг за шагом проясняя значение этой строчки. Нашей первой попыткой будет дословный перевод:

«Не существует чисел а и а' таких, что они оба:

(1) составляют пару доказательства ТТЧ и

(2) а' является арифмоквайнификацией d».

Мы знаем, однако, что существует число а', являющееся арифмоквайнификацией d. Следовательно, дело в другом числе, в а. Это позволяет нам перефразировать наш перевод:

«Не существует такого числа а, которое составляло бы пару доказательства ТТЧ с арифмоквайнификацией d»

(Этот шаг может быть немного сложным для понимания; ниже мы остановимся на нем подробнее.) Видите ли вы, что происходит? G утверждает, что:

«Формула, чей Гёделев номер — арифмоквайнификация d, не является теоремой ТТЧ».

Но — и это уже не должно нас удивлять — эта формула не что иное, как сама строчка G! Следовательно, нашим окончательным переводом будет:

«G — не теорема ТТЧ»;

или, если вам так больше нравится —

«Я — не теорема ТТЧ».

Начав с интерпретации на низшем уровне — суждения теории чисел, мы постепенно дошли до интерпретации на высшем уровне — суждения мета-ТТЧ.

ТТЧ выбрасывает полотенце

В главе IX мы уже упоминали о главном следствии этого удивительного построения: это неполнота ТТЧ. Давайте вспомним, как мы при этом рассуждали:

Является ли G теоремой ТТЧ? Если это так, то она должна утверждать истинный факт. Но что именно утверждает G? Свою собственную нетеоремность. Следовательно, из ее теоремности вытекала бы ее нетеоремность. Противоречие!