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

Отсюда следует типично «наследственное» заключение: величина I никогда не может стать делимой на 3. В частности, 0— пример запрещенной величины I . Таким образом, MU не является теоремой системы MIU.

Обратите внимание, что даже в форме головоломки о величине I , эта проблема все еще усложнена игрой удлиняющих и укорачивающих правил. Нашей целью было прийти к нулю; величина I могла увеличиваться (правило II) или уменьшаться (правило III). До анализа ситуации мы могли считать, что применив эти два правила достаточное количество раз, когда-нибудь мы смогли бы получить 0. Теперь, благодаря простому доказательству теории чисел, мы знаем, что это невозможно.

Не все проблемы подобного типа решаются так легко. Однако мы видели, что по крайней мере одна такая головоломка может быть введена в теорию чисел и решена там. Теперь мы увидим, что в теорию чисел возможно включить все проблемы о любой формальной системе. Это возможно сделать благодаря открытию Гёделем специального типа изоморфизма. Я проиллюстрирую его на примере системы MIU.

Рассмотрим для начала нотацию этой системы. Каждому ее символу будет соответствовать новый символ:

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 — любое натуральное число, меньшее 10 m .

ПРАВИЛО 1: Если мы получили 10 m + 1, то мы можем получить 10 * (10 m + 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)