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

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

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

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

Я не буду слишком долго держать вас в неведении относительно происхождения этих замечательных графиков. INT (сокращенное interchange – обмен) связан с проблемой непрерывных дробей, а еще точнее – «последовательностей ETA». В основе INT лежит идея о том, что знаки плюс и минус взаимозаменяемы для определенного вида непрерывных дробей. Отсюда следует то, что INT(INT(x))=x. Когда x рационально, ITN(x) также рациональна; квадратичные значения x дают квадратичные значения INT(x). He знаю, верна ли эта тенденция для высших алгебраических степеней. Другим любопытным свойством INT является то, что в точках рациональных значений x функция разрывается скачками, в то время как в точках иррациональных значений x она непрерывна.

Рис. 34. График G: рекурсивный график, показывающий энергетические полосы для электронов в идеализированном кристалле, помещенном в магнитное поле. a, представляющая силу магнитного поля, изменяется вертикально от 0 до 1.Энергия показана на горизонтальной оси. Сегменты горизонтальных линий – разрешенные энергии электронов.

График G представляет собой сильно упрощенный ответ на вопрос «Какую энергию может иметь электрон в кристалле, помещенном в магнитное поле?» Это очень интересная проблема, так как она совмещает две фундаментальные физические ситуации: электрон в совершенном кристалле и электрон в однородном магнитном поле. Решения этих простых проблем хорошо известны и кажутся почти несовместимыми; тем интереснее выяснить, как природе удается их совместить. Оказывается, что ситуации «электрон в кристалле без магнитного поля» и «электрон в магнитном поле без кристалла» все-таки имеют одну общую черту: в обоих случаях электрон ведет себя периодично во времени. Когда две ситуации совмещаются, отношение их периодов является ключевым параметром, так как оно выражает возможные уровни энергии электронов. Однако свой секрет это отношение выдает только тогда, когда оно записано в форме непрерывной дроби.

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

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

У читателя может возникнуть вопрос, можно ли получить такую сложную структуру экспериментальным путем. Честно говоря, я бы сам удивился больше всех, если бы в результате какого-нибудь эксперимента получился График G. График G «физичен» в том смысле, что он указывает, как можно математически подходить к менее идеальным физическим проблемам. Другими словами, График G принадлежит к области теоретической физики, а не указывает физикам-практикам на то, что они могут получить в результате экспериментов. Как-то раз один из моих друзей-агностиков, пораженный бесконечным количеством бесконечностей Графика G, именовал этот график «портретом Бога» – и это совсем не показалось мне богохульством.

Рекурсия на низшем уровне материи

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

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

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

Давайте теперь перейдем на более конкретные темы и ограничимся двумя частицами – электронами и фотонами. Нам также придется включить сюда и античастицу электрона – позитрон. (Фотон является античастицей себя самого.) Вообразите себе скучный мир, в которой голый электрон желает добраться от точки А до точки В, как Зенон в моей «Трехголосной инвенции».

Физик нарисовал бы такую картину:

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

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

По мере того, как электрон распространяется, он может испускать и снова поглощать один фотон за другим, иногда вкладывая один фотон в другой, как показано на рисунке ниже:

Математические выражения, соответствующие этим диаграммам – так называемым «диаграммам Файнмана» – легко записать, но труднее вычислить, чем соответствующие выражения для голых электронов. Самое сложное то, что фотон – реальный или виртуальный – может на мгновение превратиться в пару электрон-позитрон. Между ними происходит аннигиляция, и, как по волшебству, первоначальный фотон появляется снова! Этот процесс показан на рисунке ниже:

Стрелка, указывающая направо, – электрон, налево – позитрон. Как вы, наверно, догадались, эти виртуальные процессы могут вставляться один в другой до любой глубины. В результате может получиться довольно сложная диаграмма, такая, как показана на рис. 35. На данной диаграмме Файнмана один электрон входит слева в точке А, и после серии удивительных акробатических трюков выходит справа в точке В. Отсюда видно, что линии как электрона, так и фотона могут быть сколько угодно «украшены». Такую диаграмму чрезвычайно трудно вычислить.

Рис. 35. Диаграмма Файнмана. показывающая распространение ренормализованного электрона от А до В. Время возрастает слева направо, это значит, что в тех местах, где стрелка указывает справа налево, электрон движется «обратно во времени». Или, говоря более интуитивно, антиэлектрон(позитрон) движется вперед во времени. Фотоны – свои собственные античастицы, и поэтому их линии не нуждаются в стрелках

У этих диаграмм своя «грамматика», позволяющая воплотиться в жизнь только определенным картинкам. Например, ситуация, изображенная ниже, невозможна:

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

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

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

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

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

Копии и схожесть

Давайте теперь снова взглянем на График G. Возможно, читатель помнит, что во введении мы говорили о разных формах канонов. Каждый тип канона использовал основную тему и копировал ее с помощью изоморфизма, или сохраняющей информацию трансформации. Иногда копии получались вверх ногами, иногда задом наперед, а иногда растянутые или сокращенные… В Графике G есть все эти типы трансформации, и даже больше. Отображение всего графика в его частях требует изменения размеров, искажения, отражения и так далее. И все же мы можем говорить о некоей основной тождественности, которую при определенном усилии можно заметить – особенно, если ваш глаз уже натренирован на INT.

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

Рис. 36. М. К. Эшер. Рыбы и чешуйки. (Гравюра на дереве, 1959).

Что именно делает всех бабочек «похожими» друг на друга? Отображение одной бабочки на другую не совпадает по клеткам; скорее, оно совпадает по функциональным органам, отчасти на макроскопическом и отчасти на микроскопическом масштабе. Вместо точных пропорций сохраняются функциональные отношения частей. Именно этот тип изоморфизма связывает между собой бабочек на гравюре Эшера «Бабочки» (рис. 37). То же верно и для более абстрактных бабочек Графика G, связанных между собой математическими отображениями одной функциональной части в другую. При этом полностью игнорируются пропорции линий, углы, и тому подобное.

Рис. 37. М. К. Эшер. «Бабочки» (гравюра на дереве, 1950).

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

Когда два предмета схожи между собой?

В этой книге мы вернемся к нему еще не раз и, рассмотрев его под всевозможными углами, увидим, насколько такой простой вопрос связан с природой разума. То, что этот вопрос возник в главе, посвященной рекурсии, не случайно, рекурсия – это область, в которой схожесть-внутри-различия играет центральную роль. Рекурсия основана на «одном и том же» событии, происходящем одновременно на нескольких различных уровнях. При этом события на разных уровнях не одинаковы – скорее мы находим в них какую-либо общую черту, как бы они не различались. Например, в «Маленьком гармоническом лабиринте» истории на разных уровнях весьма отличны друг от друга, и их схожесть заключается лишь в двух фактах: (1) все они – истории и (2) во всех историях действуют Ахилл и Черепаха. В остальном, эти истории радикально отличаются одна от другой.

Программирование и рекурсия: модульность, петли, процедуры

Одна из основных способностей, необходимых в компьютерном программировании, – это умение заметить, когда два явления схожи в широком смысле, поскольку это ведет к модуляризации – разбиванию задачи на несколько естественных подзадач. Представьте, например, что вам надо исполнить одну за другой серию схожих операций. Вместо того, чтобы записывать каждую из них, мы можем написать петлю (или цикл), которая говорит компьютеру, что, выполнив некое множество операций, он должен вернуться к началу и повторять тот же процесс снова и снова, пока не будет выполнено некое условие. Тело петли – определенные повторяющиеся команды – не должно быть жестко установленным; в нем допустимы предсказуемые вариации. Примером может служить несложная проверка того, является ли число N простым. Вначале вы делите число N на 2, потом на 3, 4, 5, и так далее, до N-1. Если N не делится ни на одно из этих чисел, то N – простое число.

Обратите внимание на то, что каждый шаг цикла здесь похож на другие, но не тождественен им. Заметьте также, что количество шагов варьируется в зависимости от N, поскольку петля постоянной длины не могла бы служить общей проверкой для простых чисел. Существуют два критерия для «прерывания» петли: (1) если N делится без остатка на какое-либо число, то петля прерывается и ответом будет «НЕТ»; (2) если мы достигли N-1 и N «выжило», не разделившись, то петля прерывается и ответом будет «ДА».

Основная идея петель такова: повторять серию родственных шагов до тех пор, пока не выполняется определенное условие. Иногда максимальное количество шагов в петле заранее известно, а иногда мы начинаем и ждем, пока петля прервется. Второй тип петель, который я называю свободными, опасен, поскольку условия для прерывания петли могут никогда не выполниться, в результате чего компьютер застрянет на так называемом «бесконечном цикле». Разница между свободными и ограниченными петлями, или циклами, является одним из важнейших понятий в теории вычислительной техники; этой теме будет посвящена глава «БлууП и ФлууП и ГлууП».

Петли могут быть также вложены одна в другую. Предположим, например, что мы хотим найти все простые числа от 1 до 5000. Для этого можно написать вторую петлю, повторяющую описанную проверку снова и снова, начиная с N=1 и кончая N=5000. Таким образом, у нашей программы будет структура «петли-в-петле». Хорошие программисты обычно составляют программы именно в этом «стиле». Подобные вложенные петли встречаются в инструкциях для сборки простых предметов, а также в таких видах деятельности, как вязание и вышивание, где маленькие петли повторяются несколько раз внутри больших петель, которые, в свою очередь, тоже повторяются несколько раз… Результатом петли на нижнем уровне может быть всего пара стежков, в то время как петля на высшем уровне производит большую часть изделия.

В музыке также часто встречаются вложенные одна в другую петли – например, когда гамма (маленькая петля) проигрывается несколько раз, возможно, сдвинутая при этом выше или ниже. Последние части Пятого концерта Прокофьева и Второй симфонии Рахманинова содержат длинные пассажи, в которых разные инструменты одновременно проигрывают гаммы-петли в быстром, среднем и медленном темпе – эффект получается потрясающий. Гаммы Прокофьева идут вверх, гаммы Рахманинова – вниз. Выбор за вами!

Более широким, чем понятие петли, является понятие подпрограммы или процедуры, которое мы уже затронули. Группа операций при этом рассматривается как одно целое, носящее определенное название – например, процедура УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ. Как мы видели в СРП, процедуры могут вызывать одна другую по имени – таким образом кратко описывается последовательность необходимых операций. Это – основа модульности в программировании. Разумеется, модульность существует также в качественных системах звуковоспроизведения, в мебели, в живых клетках и в человеческом обществе – везде, где есть иерархическая структура.

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

Рекурсия в шахматных программах

Классическим примером рекурсивной процедуры с параметрами может служить программа для выбора лучших ходов в шахматной партии. Лучшим ходом можно, по-видимому, считать тот, что оставляет противника в наихудшей ситуации. Таким образом, проверка лучшего хода весьма проста: представьте себе, что вы сделали ход… а теперь мысленно переверните доску и оцените позицию с точки зрения вашего противника. Но каким образом оценивает позицию ваш противник? Он ищет свой лучший ход. Это значит, что он мысленно перебирает все возможные варианты и оценивает их, как ему кажется, с вашей точки зрения, надеясь, что вы найдете их опасными для себя. Обратите внимание, что мы определили «лучший ход» рекурсивно: то, что лучше для одного противника, хуже для другого. Рекурсивная процедура, занятая поисками лучшего хода, пробует один ход за другим и каждый раз вызывает саму себя в качестве противника! В этой роли она пробует следующий ход, и вызывает себя в качестве противника противника – то есть, снова себя самой.

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

В программах подобного «игрового» типа, каждый анализируемый ход порождает «дерево анализа вариантов», где сам ход является стволом, возможные ответы – основными ветвями, контр-ответы – ветвями потоньше, и так далее. На рис. 38 я показал простое дерево анализа, иллюстрирующее начало игры в крестики-нолики. Существуют способы, позволяющие избежать анализа каждой ветви до конца. В искусстве выращивания шахматных деревьев лидируют люди, а не компьютеры. Известно, что лучшие игроки просчитывают варианты на относительно небольшое число ходов, в сравнении с компьютером – и играют при этом намного лучше! В начале развития компьютерных шахмат считалось, что не пройдет и десяти лет, как компьютер (или программа) станет чемпионом мира. Однако, эта цель не достигнута и по сей день… Это может служить еще одним подтверждением очень рекурсивного

Закона Хофштадтера:

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

Рис. 38. Разветвляющееся дерево ходов и контрходов в начале игры в крестики и нолики.

Рекурсия и непредсказуемость

В чем связь между рекурсивными множествами предыдущей главы и рекурсивными процедурами этой главы? Ответ на этот вопрос затрагивает понятие рекурсивно перечислимых множеств. Чтобы множество было р.п., оно должно быть получено на основе начальных точек (аксиом) при помощи повторного применения правил вывода. Таким образом, множество растет и растет, и каждый новый элемент так или иначе составлен из предыдущих – что-то вроде «математического снежного кома». Но ведь это и есть основа рекурсии: вместо явного определения нечто определяется через более простые версии себя самого. Числа Фибоначчи и Лукаса – превосходные примеры р.п. множеств, вырастающих из двух данных элементов до бесконечности путем применения рекурсивного правила. По соглашению, множество, чье дополнение также р.п., называется «рекурсивным».

Рекурсивное перечисление – это процесс, в котором новые элементы вырастают из старых при помощи определенных правил. В подобных процессах немало сюрпризов – например, непредсказуемость ряда Q. Может показаться, что подобные рекурсивно определенные ряды обладают некой врожденной возрастающей сложностью поведения – чем дальше вы идете, тем менее предсказуемы они становятся. Развивая эту идею, мы приходим к мысли, что достаточно сложная рекурсивная система может быть настолько мощной, что она в конце концов вырвется за пределы любой установленной заранее схемы. Но не это ли одно из основных свойств разума? Вместо того, чтобы рассматривать программы, просто вызывающие самих себя, нельзя ли попытаться создать изменяющиеся программы – программы, действующие на другие программы, улучшая, расширяя, обобщая и налаживая их? В самом сердце разума, возможно, лежит именно такой тип «переплетающейся рекурсивности».