ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Хофштадтер Даглас Р. (читать полные книги онлайн бесплатно .txt) 📗

M <==> 3

I <==> 1

U <==> 0

Это соответствие — вполне произвольно; я выбрал его потому, что эти символы слегка похожи на те, которым они соответствуют. Каждый номер называется Гёделев номер соответствующей буквы. Уверен, что вы можете легко догадаться, как будет выглядеть Гёделев номер строчки из нескольких букв:

MU <==> 30

MIIU <==> 3110

и т. д.

Это нетрудно. Ясно, что такое соответствие между двумя нотациями является превращением, сохраняющим информацию; это все равно, что одна и та же мелодия, исполненная на двух разных инструментах.

Теперь давайте посмотрим на типичную деривацию системы MIU, записанную одновременно в двух нотациях:

(1)            MI -- аксиома    -- 31

(2)           МII -- правило II  -- 311

(3)         MIIII -- правило II  -- 31111

(4)         MUI -- правило III -- 301

(5)       MUIU -- правило I   -- 3010

(6)  MUIUUIU -- правило II  -- 3010010

(7)      MUIIU --  правило IV -- 30110

Левая колонка получается при помощи наших четырех формальных типографских правил. О правой колонке можно сказать, что она также получилась в результате применения подобных правил. Однако правая колонка — дуалистична. Сейчас я объясню, чти это означает.

 О пятой строчке («3010») можно сказать, что она была сделана из четвертой добавлением «0» справа; с другой стороны, мы можем так же легко представить себе, что она была получена в результате арифметической операции — а именно, умножения на 10. Когда натуральные числа записаны в десятичной системе, умножение на 10 и добавление справа «0» неотличимы друг от друга. Мы можем воспользоваться этим и записать арифметическое правило, соответствующее типографскому правилу I:

АРИФМЕТИЧЕСКОЕ ПРАВИЛО Iа: Число, десятичное продолжение которого оканчивается справа на «1», может быть умножено на 10.

Мы можем избавиться от упоминания символов в десятичном продолжении, арифметически описав правую цифру:

АРИФМЕТИЧЕСКОЕ ПРАВИЛО Ib: Если при делении некоего числа на 10 в остатке получается «1», то это число может быть умножено на 10.

Можно было бы воспользоваться и чисто типографским правилом, как, например, следующее:

ТИПОГРАФСКОЕ ПРАВИЛО I: Из любой теоремы, которая кончается на «1», можно получить новую теорему, добавляя «0» справа от этой «1».

Все эти правила дают одинаковый эффект. Именно поэтому правая колонка дуалистична: ее можно рассматривать как серию типографских операций, превращающих одну схему символов в другую, или как серию арифметических операций, превращающих одну величину в другую. Существуют веские причины к тому, чтобы больше интересоваться арифметической версией. Переход из одной чисто типографской системы в другую, изоморфную типографскую систему — это не слишком занимательно; с другой стороны, переход из типографской области в изоморфную ей часть теории чисел предоставляет интересные, ранее неиспользованные возможности. Словно кто-то всю жизнь имел дело только с нотной записью, и вдруг ему показали соответствие между нотами и звуками. Какой удивительное богатство открылось перед ним! Или, возвращаясь к Ахиллу и Черепахе, играющим с цепочками, представьте себе человека, который хорошо знаком с фигурами из цепочек, и которому вдруг открылось соответствие между цепочками и рассказами. Какое откровение! Открытие Геделевой нумерации сравнивают с открытием Декарта, установившего изоморфизм между линиями на плоскости и уравнениями с двумя переменными. Это кажется невероятно просто — но это открывает дорогу в огромный новый мир.

Однако прежде чем придти к заключению, давайте рассмотрим подробнее этот высший уровень изоморфизма. Это очень хорошее упражнение. Наша цель — придумать арифметические правила, действующие точно так же, как типографские правила системы MIU.

Ниже приведено решение. В этих правилах m и k - произвольные натуральные числа, и n — любое натуральное число, меньшее 10m.

ПРАВИЛО 1: Если мы получили 10m + 1, то мы можем получить 10 * (10m + 1).

Пример: Переход от строчки 4 к строчке 5. Здесь m = 30

ПРАВИЛО 2: Если мы получили 3 * 10^m + n, то мы можем получить 10^m * (3 * 10^m + n) + n

Пример: Переход от строчки 1 к строчке 2, где n и m равняются 2.

ПРАВИЛО 3: Если мы получили k *10 ^m+3 + 111 * 10^m + n, то мы можем получить k * 10 ^m+1 + n.

Пример: Переход от строчки 3 к строчке 4. Здесь m и n равняются 1 и k равняется 3.

ПРАВИЛО 4: Если мы получили k * 10^{m +2} + n, то мы можем получить k * 10 ^m + n.

Пример: Переход от строчки 6 к строчке 7. Здесь m=2, n=10 и k=301.

Не следует забывать нашу аксиому! Без нее мы как без рук, так что давайте запишем постулат.

Мы можем получить 31.

Теперь правую колонку можно рассматривать как арифметический процесс в новой арифметической системе, которую мы назовем системой 310:

(1)         31       аксиома

(2)        311       правило 2 (m = 1, n = 1)

(3)      31111       правило 2 (m = 2, n = 11)

(4)        301       правило 3 (m = 1, n = 1, k = 3)

(5)       3010       правило 1 (m = 30)

(6)    3010010       правило 2 (m = 3, n = 10)

(7)      30110       правило 4 (m = 2, n = 10, k = 301)

Обратите внимание на то, что удлиняющие и укорачивающие правила снова с нами и в системе 301; они просто переведены в область чисел таким образом, что Гёделевы номера в системе возрастают и уменьшаются. Если вы посмотрите внимательно на то, что происходит, то увидите, что правила основаны на простой идее, а именно: сдвиг цифр направо и налево в десятичной записи чисел имеет отношение к умножению на степени числа 10. Это простое наблюдение обобщено в следующем центральном предложении:

ЦЕНТРАЛЬНОЕ ПРЕДЛОЖЕНИЕ: Если у нас имеется некоторое правило, говорящее нам, как определенные цифры могут быть передвинуты, заменены, добавлены или опущены в в десятичной записи любого числа, то это правило также может быть представлено соответствующим арифметическим правилом при помощи арифметических операций со степенями числа 10, а также сложения, вычитания и так далее.

Или короче:

Типографские правила манипуляции с символами чисел эквивалентны арифметическим правилам операций с числами.

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

Подобно тому, как набор типографских правил порождает набор теорем, в результате повторного применения арифметических правил получается соответствующее множество натуральных чисел. Эти выводимые числа играют ту же роль в теории чисел, как теоремы — в любой формальной системе. Разумеется, набор выводимых чисел изменяется в зависимости от принятых правил. «Выводимые числа» выводимы только относительно данной системы арифметических правил. Например, такие числа как 31, 3010010, 31111 и так далее могут быть названы выводимыми в системе MIU. Это неуклюжее название можно сократить до чисел MIU; оно символизирует тот факт, что эти числа — результат перевода системы MIU в теорию чисел при помощи Гёделевой нумерации. Если бы мы захотели приложить Гёделеву нумерацию к системе pr и затем «арифметизировать» ее правила, мы могли бы называть полученные числа «числами pr» — и так далее.