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

140

Замена подводит нас ко второй идее

Предыдущее обсуждение показало нам, как ТТЧ может «анализировать» понятие теоремности ТТЧ. Это — основа первой части доказательства. Перейдем теперь ко второй идее доказательства, путем развития понятия, позволяющего сконцентрировать этот «самоанализ» в одной единственной формуле. Для этого давайте посмотрим, что случается с Гёделевым номером какой-либо формулы, когда ее структура слегка меняется. Рассмотрим следующее изменение:

замена всех свободных переменных на определенные символы чисел.

Ниже, в левой колонке, даны два примера этой операции; в правой колонке показаны параллельные изменения в Гёделевых номерах.

Формула                                                         Геделев номер

a=a                                                                 262,111,262

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

SS0=SS0                                                          123,123,666,111,123,123,666

                                                         *******

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

.                                                                    262,163,163,111,362,123,123,262,

.                                                                    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а':

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

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

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

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