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

Наша формальная система — назовем ее системой 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.

Теперь у вас есть все, что нужно, чтобы попытаться вывести MU. Не волнуйтесь, если у вас не будет получаться; просто попробуйте поиграть с системой и постарайтесь схватить суть головоломки MU. Надеюсь, что вы получите удовольствие!

Ответ на головоломку MUвы найдете дальше в тексте. Сейчас для нас важен сам процесс поиска решения. Возможно, что вы уже попытались это сделать; если так, то теперь у вас оказалась целая коллекция строчек. Подобные строчки, выведенные путем применения правил, называются теоремами. Термин «теорема», разумеется, широко используется в математике и имеет там совсем другое значение: какое-либо утверждение на естественном языке, доказанное с помощью строгих рассуждений (например, Теорема Зенона о «невозможности» движения или Теорема Эвклида о бесконечном количестве простых чисел). Однако в формальных системах теоремы — не утверждения, а лишь строчки символов. Такие теоремы не доказываются, а просто производятся автоматически при помощи неких типографских правил. Чтобы подчеркнуть это важное отличие, в дальнейшем, говоря о «теоремах» в обыденном значении, я буду писать это слово с заглавной буквы: Теорема — это утверждение на каком-либо естественном языке, которое было доказано с помощью логических рассуждений. Слово «теорема», написанное с маленькой буквы, будет употребляться в техническом значении: теорема — это строчка, выводимая в какой-либо формальной системе. В этих терминах головоломка MUсостоит в том, чтобы выяснить, является ли MUтеоремой системы MIU.

В начале этой главы я «подарил» вам теорему MI. Такая «дареная» теорема называется аксиомой. Также и в этом случае, техническое значение этого слова отличается от повседневного. Формальная система может иметь ноль, одну, несколько и даже бесконечное множество аксиом. Далее в книге приводятся примеры формальных систем всех трех видов.

Каждая формальная система обладает набором правил обращения с символами, таких, как четыре правила системы MIU. Подобные правила называются порождающими правилами или правилами вывода ; в дальнейшем я буду пользоваться обоими терминами.

И, наконец, последний термин — вывод. Ниже приводится вывод теоремы MUIIU:

(1) MI аксиома

(2) MII из (1) по правилу II

(3) MIIII из (2) по правилу II

(4) MIIIIU из (3) по правилу I

(5) MUIU из (4) по правилу III

(6) MUIUUIU из (5) по правилу II

(7) MUIIU из (6) по правилу IV

Выводом теоремы называется последовательное, шаг за шагом, объяснение того, как можно получить данную теорему согласно правилам формальной системы. Понятие вывода основывается на понятии доказательства, являясь, однако, лишь его дальним родственником. Было бы странным утверждать, что мы доказали строчку MUIIU; скорее, мы ее вывели.

Большинство читателей, пытаясь решить головоломку MU, начинает выводить теоремы наобум и смотрят, что при этом получается. Вскоре, однако, они замечают, что полученные теоремы обладают некими свойствами; в этот момент в работу включается разум. Возможно, что пока вы не вывели несколько теорем, для вас не было очевидным, что все они будут начинаться с M. В какой-то момент вы заметили некую закономерность и смогли ее объяснить, исходя из правил они таковы; что каждая новая теорема наследует первую букву предыдущей. В результате первые буквы всех теорем восходят к первой букве нашей единственной аксиомы MI— и это доказательство того, что все теоремы системы MIUдолжны начинаться с M.