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

Хофштадтер Даглас Р.

Зенон: Ах, какой стыд. Конечно же, вы правы. Это тот парадокс, где объясняется, что идя от А до Б, надо сначала пройти половину пути — но от этой половины также придется сначала пройти половину… и так далее. Оба эти парадокса очень похожи; честно говоря, я просто обыгрывал мою Великую Идею с разных сторон.

Ахилл: Могу поклясться, что эти аргументы содержат ошибку. Хотя я не вижу, где в них ошибка, зато прекрасно понимаю, что они не могут быть верными.

Зенон: Так вы сомневаетесь в правильности моих парадоксов? Отчего же вам самим не попробовать?

Видите тот красный флаг в конце дорожки?

Ахилл: Невозможный, сделанный по гравюре Эшера?

Зенон: Тот самый. Как насчет того, чтобы вам с Черепахой пробежаться к флагу наперегонки? Конечно, ей надо будет дать приличную фору, скажем…

Черепаха: Как насчет пятидесяти локтей?

Зенон: Отлично — пусть будут пятьдесят локтей.

Ахилл: Я-то всегда готов.

Зенон: Вот и чудесно. Все это захватывающе интересно! Сейчас мы проверим мою строго доказанную Теорему на опыте! Госпожа Черепаха, будьте так добры, займите позицию на пятьдесят локтей впереди Ахилла.

(Черепаха продвигается на пятьдесят локтей ближе к флагу.)

Ну как, вы оба готовы?

Черепаха и Ахилл: Готовы!

Зенон: На старт… Внимание… Марш!

ГЛАВА I: Головоломка MU

Формальные системы

ОДНИМ ИЗ центральных понятий этой книги является понятие формальной системы. Формальные системы того типа, который я использую, были изобретены американским логиком Эмилем Постом в 1920-х годах; их часто называют системами продукции или системами Поста. Эта глава познакомит вас с одной из таких формальных систем. Надеюсь, что вам захочется хотя бы немного ее исследовать — чтобы вас заинтересовать, я придумал небольшую головоломку.

Головоломка формулируется просто: «Можете ли вы получить MU?» Для начала вам будет дана некая строчка (последовательность букв).^{1} Чтобы не мучить вас неизвестностью, сообщу эту строчку сразу — это будет MI. Кроме этого, вам будут даны правила, с помощью которых вы сможете превращать одну строчку в другую. Вы можете использовать любое правило, применимое в данный момент; при этом, если таких правил несколько, у вас имеется свободный выбор. Именно в этот момент игра с формальной системой ближе всего подходит к искусству. Само собой, главное требование игры — следование правилам. Это ограничение может быть названо «требованием формальности». Возможно, что в данной главе нам не придется подробно на нем останавливаться. Однако, как бы удивительно это вам не казалось, работая с формальными системами последующих глав, вы увидите, что вам частенько захочется нарушать требование формальности, если у вас раньше не было навыка работы с подобными системами.

Наша формальная система — назовем ее системой MIU — использует лишь три буквы: М, U, I. Это означает, что единственными строчками системы MIU будут те, которые используют только эти буквы. Ниже приводятся некоторые строчки системы MIU:

MU

UIM

MUUMUU

UIIUMIUUIMUIIUMIUUIMUIIU

Однако,

хотя все эти строчки и правильны, вы еще не можете ими распоряжаться. Пока у вас имеется единственная строчка — MI. Вы можете расширить вашу «коллекцию» путем применения правил. Первое правило нашей системы:

ПРАВИЛО I: Если у вас есть строчка, кончающаяся на I, вы можете прибавить U в конце.

Кстати, надо отметить, если вы уже сами об этом не догадались, что в понятии «строчка» важен определенный порядок букв. Например, MI и IM — две разные строчки. Строчка символов совсем не то же самое, что «мешок» с символами, где порядок символов не играет никакой роли.

Второе правило нашей системы:

ПРАВИЛО II: Если у вас имеется Мx, вы можете прибавить к вашей коллекции Мxx.

Поясним это правило на нескольких примерах.

Из MIU вы можете получить MIUIU.

Из MUM вы можете получить MUMUM.

Из MU вы можете получить MUU.

Таким образом, буква x означает здесь любую строчку; однако, после того, как вы выбрали определенную строчку, вам придется держаться вашего выбора до тех пор, пока вы не используете снова то же правило — тогда вы можете сделать новый выбор. Обратите внимание на третий пример. Он показывает, каким образом вы можете получить новую строчку из MU — но сначала вам необходимо иметь в вашей коллекции MU! Хочу добавить еще одно, последнее замечание, касающееся буквы «x» она не является частью формальной системы в том смысле, как буквы «М», «I» и «U». Тем не менее, нам нужен способ говорить о строчках системы вообще — и в этом нам помогает «x», символизирующий любую произвольную строчку. Если в вашей коллекции оказывается строчка, содержащая «x», это значит, что вы где-то ошиблись, так как в строчках системы MIU эта буква не встречается.

Третье правило нашей системы:

ПРАВИЛО III: Если в какой-либо строчке встречается III, вы можете получить новую строчку, где вместо III будет U.

Примеры.

Из UMIIIMU вы можете получить UMUMU.

Из MIIII вы можете получить MIU (а также MUI).

Из IIMII вы не можете, применяя правило III, получить ничего нового. (Все три I должны стоять подряд.)

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

Из MU можно получить MIII. <= Это неверно.

Все правила читаются только в одном направлении, слева направо.

Последнее правило нашей системы:

ПРАВИЛО IV: Если в какой-либо строчке встречается последовательность UU, вы можете ее опустить.

Из UUU можно получить U. Из MUUUIII можно получить MUIII.