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

Автор книги: Даглас Хофштадтер

сообщить о нарушении

Текущая страница: 9 (всего у книги 64 страниц)

ГЛАВА III: Рисунок и фон

Простые и составные числа

ТО, ЧТО некоторые понятия можно выразить при помощи простых манипуляций типографскими символами, кажется довольно странным. До сих пор мы передали таким образом лишь понятие сложения, и это, возможно, не показалось нам удивительным. Предположим, однако, что мы захотим создать формальную систему с теоремами вида Px, где x было бы строчкой, состоящей из тире. Количество этих тире должно было бы выражаться простым числом. Так, P– – было бы теоремой, в то время как P– теоремой бы не являлось. Как это может быть выражено с помощью типографских операций? Сначала необходимо точно определить, что мы имеем в виду под «типографскими операциями». Полное описание было дано в системах MIU и pr, так что сейчас мы ограничимся только списком наших возможностей:

(1) читать и узнавать любое из конечных множеств символов;

(2) записывать любой из символов, принадлежащий такому множеству,

(3) повторять любой из этих символов в другом месте;

(4) стирать любой из этих символов;

(5) проверять, одинаковы ли два символа;

(6) сохранять и использовать список ранее выведенных теорем.

Список получился немного повторяющимся, но это не столь важно. Главное то, что он позволяет только самые тривиальные операции, намного проще, чем операция отличения простого числа от не простого. Как же, в таком случае, мы сможем совместить несколько операций и создать такую формальную систему, в которой простые числа отличались бы от составных?

Система ur

Первым шагом может стать решение более простой, но сходной задачи. Мы можем попытаться придумать систему, похожую на систему pr, но которая вместо сложения представляла бы умножение. Назовем ее системой ur (u = «умноженное на»). Предположим, что X, Y, Z , соответственно, – это количество тире в строчках x, y, z. (Обратите внимание, что я специально делаю упор на различии между строчкой, и количеством тире, которое эта строчка содержит.) Мы хотим, чтобы строчка xuyrz была теоремой только в том случае, когда X, умноженное на Y, равняется Z. Например, –u–r– должно быть теоремой, так как 2, умноженное на 3, равняется 6, в то время как –u–r– теоремой быть не должно. Систему ur так же просто описать, как и систему pr. Для этого нужны всего лишь одна аксиома и одно правило вывода

СХЕМА АКСИОМ: xu-rx является аксиомой, когда x – строчка, состоящая из тире.

ПРАВИЛО ВЫВОДА: Предположим, что x, у, и z – строчки тире, и что xuyrz – старая теорема. Тогда xuy-rzx будет новой теоремой.

Ниже приводится вывод теоремы –u–r–

(1) –u-r– (аксиома)

(2) –u–r– (по правилу вывода, используя (1) в качестве старой теоремы)

(3) –u–r– (по правилу вывода, используя (2) в качестве старой теоремы)

Обратите внимание, что количество тире в средней строке возрастает на единицу каждый раз, когда мы применяем правило вывода, таким образом, мы можем предсказать, что если мы хотим получить теорему с десятью тире в середине, нам придется применить правило вывода девять раз подряд.

Уловление Составности

Умножение (немного более сложное понятие, чем сложение) теперь уловлено нами в сети типографских правил, подобно птицам в Эшеровском «Освобождении». А как же насчет простых чисел? Следующий план кажется неплохим: используя систему ur, определить новое множество теорем вида Sx, которые характеризуют составные числа

ПРАВИЛО: Предположим, что x, у, z – строчки тире. Если x-uy-rz является теоремой, то Sz также будет теоремой.

Это означает, что Z (число тире в z) является составным, если оно – произведение двух чисел, больших единицы (а именно, X+1 – число тире в x- и Y+1 – число тире в y-). Я объясняю вам это новое правило в «интеллектуальном режиме», поскольку вы, как существо мыслящее, желаете знать, почему такое правило существует. Если бы вы работали исключительно в «механическом режиме», вам бы не понадобились никакие объяснения, так как работающие в режиме M следуют правилам чисто механически, никогда не задавая вопросов, и при этом совершенно счастливы!

Поскольку вы работаете в режиме I, вы будете склонны забывать о различии между строчками и их интерпретацией. Ситуация может стать довольно запутанной, как только вы обнаружите смысл в символах, которыми вы манипулируете. Вам придется бороться с собой, чтобы не решить, что строчка «–» – то же самое, что число 3. Требование формальности, казавшееся совершенно очевидным в главе I, здесь становится весьма каверзным и приобретает первостепенную важность Именно оно не дает вам спутать режим I с режимом M, иными словами, оно не позволяет вам смешивать арифметические факты с типографскими теоремами.

«Нелегальная» характеристика простых чисел

Весьма соблазнительно от теорем типа S сразу перескочить к теоремам типа P, путем введения следующего правила

ПРЕДЛОЖЕННОЕ ПРАВИЛО: Предположим, что x – строчка тире. Если Sx не является теоремой, то Px является теоремой.

Роковая ошибка здесь заключается в том, что проверка «нетеоремности» Sx – не типографская операция. Чтобы узнать наверняка, что MU – не теорема MIU, нам пришлось бы выйти из системы; в такую же ситуацию мы попадаем и с Предложенным Правилом. Оно подрывает сами основы формальных систем тем, что предлагает вам действовать неформально, вне системы. Типографская операция (6) позволяет вам рассматривать предварительно выведенные теоремы; однако Предложенное Правило отсылает вас к гипотетической «таблице не-теорем». Чтобы получить подобную таблицу, вам придется работать вне системы, показывая, почему некоторые строчки не могут быть получены в данной системе. Конечно, может оказаться, что существует другая формальная система, в которой «таблица не-теорем» может быть получена чисто типографскими способами. На самом деле, наша цель – найти именно такую систему.Однако Предложенное Правило – не типографское, а посему нам придется от него отказаться.

Это настолько важный момент, что мы остановимся на нем поподробнее. В нашей системе S (включающей систему ur и правила, определяющие теоремы типа S) у нас есть теоремы вида Sx, где x, как обычно, обозначает строчку тире. В ней имеются также не-теоремы вида Sx. Говоря о не-теоремах, я имею в виду именно эту разновидность, хотя, конечно, существует множество не-теорем в виде неправильно сформированных строчек: u u-S r r и пр. Между теоремами и не-теоремами есть следующая разница: количество тире в первых – составное число, во вторых – простое. К тому же, все теоремы похожи по форме, так как все они выведены при помощи одного и того же набора типографских правил. Можем ли мы сказать, что в этом смысле все не-теоремы также имеют что-то общее в форме? Ниже приводится список теорем типа S, без их вывода. Число в скобках указывает на количество тире в соответствующей теореме.

S– (4)

S– (6)

S– (8)

S– (9)

S– (10)

S– (12)

S– (14)

S– (15)

S– (16)

S– (18)

.

.

.

«Дырки» в этом списке как раз и являются не-теоремами. Есть ли у них какая-то общая «форма»? Можно ли предположить, что лишь постольку, поскольку они являются пробелами в неком упорядоченном списке, они обладают какими-то общими чертами? И да, и нет. Нельзя отрицать, что у них есть общие типографские черты; вопрос в том, правомочно ли называть эти черты «формой». Дело в том, что дырки определены только негативно: они представляют из себя то, что осталось от позитивно определенного списка.

 Рисунок и фон

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

Существуют замечательные шрифты, обыгрывающие это различие между рисунком и фоном. Послание, написанное таким шрифтом, приводится ниже. На первый взгляд это просто несколько клякс; но если вы посмотрите на них издали, попристальнее, то увидите семь букв на этом РИСУНКЕ (специальным шрифтом, так, что черный фон, создающий белые буквы, похож на кляксы.)

Рис. 15. Рисунок

Такой же эффект производит мой рисунок «Знак из дыма» (рис. 139). Продолжая в том же ключе, попробуйте решить следующую задачку: возможно ли нарисовать такую картину, чтобы слова были как на рисунке, так и в фоне?

Давайте условимся различать между двумя типами рисунков: курсивно рисуемыми и рекурсивными (эти термины не являются общеупотребительными – их придумал я сам). В курсивно рисуемом рисунке фон является лишь побочным продуктом. В рекурсивном рисунке, наоборот, фон может рассматриваться как отдельный самостоятельный рисунок. Обычно художник делает это вполне сознательно. Приставка «ре» здесь выражает тот факт, что как рисунок, гак и фон могут быть нарисованы курсивно, то есть, такая картина «дву-курсивна». Любой контур на рекурсивном рисунке – это обоюдоострый меч. М. К. Эшер был мастером подобных картин; взгляните, например, на его великолепную рекурсивную гравюру «Птицы» (рис. 16).

Рис. 16. M. K. Эшер. «Деление пространства при помощи птиц» (из блокнота 1942 года).

Различие здесь не такое строгое, как в математике; кто может с уверенностью утверждать, что некий фон не является в то же время и рисунком? При достаточно внимательном рассмотрении, любой фон не лишен собственного интереса. В этом смысле любой рисунок можно назвать рекурсивным. Однако, вводя эти термины, я имел в виду нечто другое. Существует естественное, интуитивное понятие узнаваемых форм. Являются ли и рисунок и фон узнаваемыми формами? Если да, то такой рисунок рекурсивен. Посмотрев на фон большинства контурных рисунков, вы обнаружите, что в нем трудно признать какую-либо форму. Это доказывает, что:

Существуют узнаваемые формы, чье негативное пространство не является никакой узнаваемой формой. Или, выражаясь более технично:

Существуют курсивно рисуемые рисунки, которые не рекурсивны.

Рис. 17. Скотт Е. Ким Рисунок «РИСУНОК-РИСУНОК».

На рис. 17 показано решение предложенной выше головоломки, принадлежащее Скотту Киму; я называю это решение «рисунок РИСУНОК – РИСУНОК». На какую бы часть – белую или черную – вы не посмотрели, вы увидите только «ФИГУРЕ» (= английское «РИСУНОК»), и никакого «ФОНА». Великолепный образчик рекурсивного рисунка! Черные области этого хитроумного рисунка можно охарактеризовать двумя способами:

(1) как негативное пространство белых областей;

(2) как видоизмененные копии белых областей (полученные путем их окраски и сдвига каждой белой области).

(В данном случае обе характеристики эквивалентны; для большинства черно-белых рисунков это не так.) В главе VIII, создавая Типографскую Теорию Чисел (ТТЧ), мы будем надеяться, что нам удастся охарактеризовать множество всех ложных утверждений аналогичными способами:

(1) как негативное пространство множества всех теорем ТТЧ;

(2) как модифицированные копии множества всех теорем ТТЧ (полученные путем отрицания каждой теоремы ТТЧ).

Однако этой надежда окажется напрасной, так как:

(1) среди множества всех не-теорем существуют некоторые истинные утверждения;

(2) вне множества всех отрицаний теорем, существуют некоторые ложные утверждения.

Отчего так получается, вы увидите в главе XIV; а пока можете поразмыслить над графическим изображением данной ситуации (Рис. 18).

Рис. 18. Эта диаграмма отношений между различными классами строчек ТТЧ весьма богата зрительным символизмом. Самый большой прямоугольник – множество всех строчек ТТЧ. Следующий прямоугольник – все правильно построенные строчки ТТЧ. Внутри него находится множество всех предложений ТТЧ. Именно на этом уровне начинают происходить интересные вещи. Множество теорем изображено в виде дерева, чей ствол – множество аксиом. Символ дерева был выбран из-за того, что оно растет «рекурсивно» новые ветви (теоремы) вырастают из старых. Пальцеобразные ветви проникают во все уголки области представляющей множество истинных высказываний, однако они не могут занять эту область целиком. Граница между областями истинных и ложных высказываний представляет собой изломанную «береговую линию», которая, как бы близко вы ее не рассматривали, всегда имеет еще более мелкие уровни структуры и таким образом, не поддается описанию каким либо конечным методом (См. книгу Мандельбродта «Фракталы» (В. Mandelbrodt Fractals)). Отраженное дерево справа представляет отрицания теорем все они ложны, но вкупе они не в состоянии заполнить всю область ложных высказываний (Рисунок автора)

Рисунок и фон в музыке

Аналогию с понятием рисунка и фона можно также найти и в музыке. Примером может служить различие между мелодией и аккомпанементом: мелодия всегда на первом плане, тогда как аккомпанемент в каком-то смысле второстепенен. Поэтому нам кажется удивительным, когда мы узнаем мелодии на «низшем» уровне музыкального произведения. Для пост-барочной музыки это редкое явление – обычно гармонии там не выходят на первый план. Но в барочной музыке – и прежде всего, у Баха – все уровни «работают» в качестве «рисунка». В этом смысле баховские композиции могут быть названы рекурсивными.

В музыке есть еще одно различие между рисунком и фоном – ударные и безударные такты. Если вы начнете отмечать ритм счетом «раз-и, два-и, три-и…», большинство нот мелодии придутся на числа, а не на «и». Иногда, однако, мелодия бывает нарочно смещена на «и», чем достигается интересный эффект. Это происходит, например, в нескольких фортепианных этюдах Шопена. Тот же прием можно найти у Баха, в особенности, в сонатах и партитурах для скрипки соло и в сюитах для виолончели соло. В этих композициях Баху удается поместить несколько мелодий одновременно на разных уровнях. Иногда он достигает этого эффекта, заставляя солирующий инструмент играть дублировки – две ноты сразу. В других случаях, однако, он помещает один голос на ударные такты, а другой – на безударные, так что слух различает две разные мелодии, вплетающиеся одну в другую и гармонически сочетающиеся. Нет нужды говорить, что Бах не останавливается на этом уровне сложности…

Рекурсивно счетные и рекурсивные множества

Перенесем понятие рисунка и фона обратно в область формальных систем. В нашем примере роль позитивного пространства играют теоремы типа S, а роль негативного пространства – строчки, в которых количество тире выражается простым числом. Пока что единственный способ, который нам удалось найти   для выражения простых чисел типографским путем, это негативное пространство. Существует ли какой нибудь способ выразить простые числа в виде позитивного пространства, то есть в виде множества теорем некой системы?

Интуиция подсказывает разным людям разные ответы. Я отчетливо помню, как был озадачен и заинтригован, заметив разницу между негативной и позитивной характеристиками. Я был совершенно уверен в том, что не только простые числа, но и вообще любое негативно определяемое множество чисел может быть определено позитивно. Интуитивное обоснование моей уверенности заключалось в следующем вопросе: «Как это возможно, чтобы рисунок и фон не содержали совершенно одинаковой информации?» Мне казалось, что они представляют собой одну и ту же информацию, закодированную двумя разными способами. А что думаете по этому поводу вы, читатель?

Выяснилось, что я был прав насчет простых чисел, но ошибался в остальном. Тогда это меня поразило и продолжает поражать и по сей день. Оказывается, что:

существуют такие формальные системы, чье негативное пространство (множество не-теорем) не является позитивным пространством никакой другой формальной системы.

Как выяснилось, этот результат сравним по глубине с Теоремой Гёделя – так что неудивительно, что моя интуиция не могла принять его сразу. Подобно математикам начала двадцатого века, я считал мир формальных систем и натуральных чисел более предсказуемым, чем он оказался в действительности. Выраженное более техническим языком, это утверждение звучит так:

Существуют рекурсивно счетные множества, не являющиеся рекурсивными.

Выражение «рекурсивно счетные» (часто сокращаемое как р.с.) – математическое соответствие нашему художественному понятию «курсивно рисуемые», а рекурсивный – соответствие «рекурсивным». Множество строчек является р. с., когда все они могут быть выведены путем применения типографских правил – например, множество теорем типа S или множество теорем системы MIU; на самом деле, это определение приложимо ко множеству теорем любой формальной системы. Оно сравнимо с понятием о «рисунке» как о «множестве линий, которые могут быть произведены в соответствии с художественными правилами» (что бы это последнее не означало!). А «рекурсивное множество» подобно рисунку, чей фон, в свою очередь, также является рисунком – в таком случае не только рисунок, но и его дополнение будут р. с. Из этого вытекает следующий результат:

Существуют такие формальные системы, у которых нет типографского алгоритма разрешения.

Из чего это следует? Очень просто. Типографский алгоритм разрешения – это метод, отличающий теоремы от не-теорем. Он позволяет нам выводить не-теоремы систематически, идя по списку всех строчек и отбрасывая те, что не являются теоремами. Эту процедуру можно назвать типографским методом вывода множества не-теорем. Однако из предыдущего утверждения (которое мы пока принимаем на веру) следует, что для некоторых формальных систем это невозможно.

Предположим, что мы нашли множество R («R» – рисунок) натуральных чисел, которое мы можем вывести каким-либо формальным путем – вроде множества составных чисел. Предположим, что его дополнением является множество F («F» – фон) – простые числа. Вместе взятые, R и F дают все натуральные числа. Мы знаем правило, позволяющее вывести все числа множества R, для чисел множества F такого правила не существует. Важно, что если числа R выводятся исключительно в возрастающем порядке, то мы всегда можем охарактеризовать F. Трудность заключается в том, что многие р. с. множества производятся при помощи таких методов, которые выводят элементы в произвольном порядке, так что не известно, появится ли какое-либо число, до сих пор пропускаемое, если подождать еще чуть-чуть.

На вопрос «Все ли рисунки рекурсивны?» мы ответили отрицательно. Теперь мы видим что придется ответить отрицательно и на аналогичный вопрос математиков «Все ли множества рекурсивны?» Имея это в виду, давайте вернемся к этому расплывчатому понятию «формы». Обратимся снова к нашим множествам R – рисунки и F – фон. Легко согласиться с тем, что все числа во множестве R имеют какую-то общую «форму» – но можно ли сказать то же самое о числах множества F? Странный вопрос. С самого начала имея дело с бесконечным множеством всех натуральных чисел, весьма сложно прямо и четко определить «дырки», остающиеся в списке после изъятия оттуда неких чисел. Таким образом, возможно что на самом деле у этих дырок нет никаких общих характеристик «формы». Неясно, стоит ли вообще использовать здесь такое соблазнительное словечко как «форма». Может быть лучше не определять этого понятия оставив ему некую интуитивную гибкость.

Вот вам еще одна головоломка, над которой вы можете поразмыслить в связи с изложенным выше Можете ли вы охарактеризовать следующее множество чисел (или его негативное пространство)?

1 3 7 12 18 26 35 45 56 69

Чем данная последовательность напоминает рисунок РИСУНОК-РИСУНОК?

Простые числа в качестве рисунка, а не фона

Как же насчет формальной системы для вывода простых чисел? Как это сделать? Способ состоит в том чтобы, не останавливаясь на умножении, обратиться прямо к неделимости, представив ее позитивно. Ниже дана схема аксиом и правило вывода теорем, представляющих понятие числа, не являющегося делителем других чисел (ND = не делитель).

СХЕМА АКСИОМ:  xyNDx, где x и у – строчки тире

Например, –ND–, где x заменен на «–» и y – на «–»

ПРАВИЛО: Если xNDy является теорема, то xNDxу также будет теоремой

Приложив это правило дважды, вы можете вывести теорему

–ND–

которая интерпретируется как «5 не делитель 12». Однако –ND– не является теоремой. В чем будет ошибка, если вы попытаетесь вывести эту строчку?

Чтобы определить, что данное число простое, у нас должны быть какие-то сведения о его свойствах неделимости. В частности, мы хотим знать, что это число не делится на 2, 3, 4, и т. д., до числа, меньшего его на единицу. Однако в формальных системах мы не можем позволить себе таких расплывчатых формулировок как «и так далее». Здесь нужна исчерпывающая точность. Нам бы хотелось иметь возможность сказать на языке системы: «число Z свободно от делителей до X» (SOD = свободно от делителей), имея в виду, что не одно число между 2 и X не является делителем Z. Это можно сделать, но здесь есть небольшой трюк. Если хотите, можете попытаться найти его.

Решение заключается в следующем:

ПРАВИЛО: Если –NDz является теоремой, то zSOD– также будет теоремой.

ПРАВИЛО: Если zSODx и x-NDz являются теоремами, то zSODx также будет теоремой.

Эти два правила, в совокупности, характеризуют понятие свободы от делителей. Все что нам нужно, это указать, что простые числа – это числа, свободные от делителей, включая число на единицу меньшее их самих:

ПРАВИЛО: Если z-SODz является теоремой, то Pz- также будет теоремой.

Не будем забывать, что 2 – тоже простое число!

АКСИОМА: P–

Вот и все, что нам необходимо. Принцип формального выражения «просто-численности» заключается в том, что существует метод проверки, не требующий никакого отступления назад. Вы всегда двигаетесь вперед, проверяя данное число на делимость – сначала на 2, потом на 3, и так далее. Именно эта «монотонность» или однонаправленность – отсутствие игры между укорачивающими и удлиняющими правилами – позволила нам уловить суть простых чисел. И именно этой потенциальной сложностью формальных систем, могущих вместить сколько угодно взаимодействий между движением вперед и назад, объясняются такие ограничивающие результаты как Теорема Гёделя и Проблема Остановки Тюринга, как и тот факт, что не все рекурсивно счетные множества рекурсивны.