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

Для начала заметьте, что правила I и IV совершенно не затрагивают величины I. Так что нам придется иметь дело только с правилами II и III. Правило III уменьшает величину I ровно на 3. После приложения этого правила величина I результата могла бы делиться на 3 — но только в том случае, если бы величина I изначальной строчки тоже делилась на 3. Короче, правило III никогда не создает числа, делящегося на 3, «из воздуха». Оно может сделать это лишь тогда, когда такое число уже имеется в начале. То же самое верно для правила II, которое удваивает величину I. Это происходит потому, что, если 2n делится на 3, то, поскольку 2 не делится на 3, то на 3 должно делиться n (простой факт теории чисел). Ни правило II, ни правило III не могут создать делящегося на 3 числа из ничего.

Но это же ключ к головоломке MU! Мы знаем следующее:

(1) Величина I начинается с 1 (1 не делится на 3);

(2) Два правила вообще не влияют на величину I;

(3) Два оставшихся правила влияют на величину I, но таким образом, что они не могут создать делимое на 3 число, если таковое не дано в начале.

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

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

Гёделева нумерация для системы MIU

Не все проблемы подобного типа решаются так легко. Однако мы видели, что по крайней мере одна такая головоломка может быть введена в теорию чисел и решена там. Теперь мы увидим, что в теорию чисел возможно включить все проблемы о любой формальной системе. Это возможно сделать благодаря открытию Гёделем специального типа изоморфизма. Я проиллюстрирую его на примере системы 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 — любое натуральное число, меньшее 10m.

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