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

Однако, хотя мы и назвали это «схемой рекурсивных переходов», мы еще не привели примера настоящей рекурсии.

Ри. 27. Схема рекурсивных переходов для УКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО  И СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО.

Рекурсия — и, по видимости, кругообразность — появляется тогда, когда мы переходим к такой СРП как СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ (Рис 27б). Как вы заметили, любая дорожка к СВЕРХУКРАШЕННОМУ СУЩЕСТВИТЕЛЬНОМУ проходит через узел УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ — таким образом, у нас обязательно появится какое-либо существительное. Мы можем на этом закончить и прийти к ФИНИШУ с «молоком» или «огромной красной голубой зеленой зевотой». Но остальные три пути к финишу сами включают рекурсивный вызов СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО. Это выглядит как порочный круг — определение чего-либо в терминах его самого. Действительно ли это происходит? На этот вопрос мы ответим так: «Да, но это не страшно.» Представьте, что в процедуре ПРЕДЛОЖЕНИЕ есть узел, вызывающий СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, и мы попадаем именно в этот узел. Это означает, что мы прежде всего запоминаем (проталкиваем в стек) место этого узла внутри ПРЕДЛОЖЕНИЯ, чтобы знать, куда нам вернуться; после этого, мы переходим к самой процедуре СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ — мы должны найти способ его сконструировать. Предположим, что мы выбираем нижнюю из двух верхних дорожек:

УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, ОТНОСИТЕЛЬНОЕ МЕСТОИМЕНИЕ, СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, ГЛАГОЛ.

Итак, за дело: сначала мы выдаем «на-гора» УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ: «странные бублики»; затем, относительное местоимение: «которые»… теперь мы должны воспроизвести СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ — но ведь мы как раз и находимся в процессе создания СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО! Это верно, но вспомните наш пример с директором, которому позвонили в середине другого телефонного разговора. Он «отложил» первый разговор в стек и начал новую беседу так, словно ничего необычного не случилось. Давайте и мы сделаем так же.

Прежде всего запасемся обратным адресом: запишем в стек, в каком узле мы находились во время второго вызова СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО. Затем снова перейдем в начало схемы, словно ничего необычного не случилось. Теперь мы должны снова выбрать путь. Давайте, для разнообразия, попробуем пройти по нижней дорожке: УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, ПРЕДЛОГ, СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ. Это значит, что сначала мы производим УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ (например, «пурпурная корова»), затем ПРЕДЛОГ (например, «без»)… и опять упираемся в рекурсию. Придется нам снова спуститься уровнем ниже — смотрите не споткнитесь! Чтобы избежать осложнений, давайте на этот раз выберем прямую дорогу. УКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ (например, «рога»). Этот вызов тут же попадает в узел КОНЕЦ, что позволяет нам вытолкнуться на предыдущий уровень. Мы обращаемся к стеку за обратным адресом, который отсылает нас к фразе «пурпурная корова без». Закончив дела на этом уровне и попав в узел КОНЕЦ, мы выталкиваемся еще раз. Теперь нам необходим ГЛАГОЛ (например, «слопала»). На этом вызов СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО на высшем уровне заканчивается. У нас получилась фраза:

«странные бублики, которые пурпурная корова без рогов слопала».

Когда мы вытолкнемся в последний раз, эта фраза будет передана наверх, к терпеливо ожидающей схеме ПРЕДЛОЖЕНИЕ.

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

Мы только что описали основные различия между круговыми и рекурсивными определениями — в последних всегда есть определенная часть без автореферентности. Таким образом, рано или поздно мы коснемся дна: наша цель — построение объекта, отвечающего определению — будет достигнута. Существуют и другие, менее прямые, чем самовызовы, пути для получения рекурсивности в СРП. Примером может служить картина Эшера «Рисующие руки» (рис. 135), где каждая процедура вызывает не саму себя, а другую. Например, можно представить СРП под названием ПРИДАТОЧНОЕ ПРЕДЛОЖЕНИЕ, вызывающую СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ, когда ей понадобится дополнение для переходного глагола — с другой стороны, высшая дорожка СВЕРХУКРАШЕННОГО СУЩЕСТВИТЕЛЬНОГО может вызывать ОТНОСИТЕЛЬНОЕ МЕСТОИМЕНИЕ и затем ПРЕДЛОЖЕНИЕ каждый раз, когда нам потребуется придаточное предложение. Это пример косвенной рекурсии; он напоминает двухступенчатую версию парадокса Эпименида.

Нет нужды говорить, что может существовать также трио процедур, вызывающих одну другую по кругу — и так далее. Может существовать даже целая семья СРП, спутанных между собой и что есть силы вызывающих друг друга и самих себя. Программа со структурой, в которой нет «высшего уровня» или «монитора», называется гетерархией (в отличие от иерархии). Этот термин изобретен Уорреном Мак Каллохом, одним из первых кибернетиков, посвятивших себя изучению мозга и интеллекта.

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

Рис. 28. СРП СВЕРХУКРАШЕННОЕ СУЩЕСТВИТЕЛЬНОЕ с одним рекурсивно расширенным узлом.

Выталкиваясь из расширенного узла, вы автоматически оказываетесь в нужном месте большой схемы. С другой стороны, находясь в маленькой схеме, вы можете конструировать внутри нее еще более миниатюрные СРП. Расширяя узлы по мере того, как вы в них попадаете, вы избегаете построения бесконечной схемы даже в том случае, когда СРП вызывает саму себя. Расширение узлов немного напоминает замену буквы в аббревиатуре на то слово, которое она представляет. Сокращение БОГ рекурсивно, но его дефект — или преимущество — заключается в том, что мы должны все время расширять букву «Б» и, таким образом, она никогда не достигнет «дна». Однако когда СРП является частью настоящей компьютерной программы, в ней всегда есть по крайней мере одна дорожка, избегающая как прямой, так и косвенной рекурсивности. Поэтому бесконечного регресса там не бывает. Даже самая гетерархическая программа рано или поздно заканчивается — иначе она вообще не работала бы! Она продолжала бы расширять узлы один за другим до скончания веков.

Бесконечные геометрические структуры могут быть определены именно так-как расширение узлов один за другим. Давайте попробуем определить бесконечную диаграмму — назовем ее «диаграммой G». Воспользуемся следующим условным обозначением, в двух узлах напишем просто букву «G», которая, однако, будет представлять всю диаграмму G. На рис. 28 показана диаграмма G, использующая такую условную нотацию. Если мы захотим представить эту диаграмму более явно, мы должны расширить каждый узел, обозначенный буквой G, то есть заменить его на уменьшенную копию той же диаграммы G (см. рис. 29 б). Эта версия диаграммы G «второго порядка» дает нам некоторое представление о том, как бы выглядела конечная, невыполнимая диаграмма G. На рис. 30 показана большая часть диаграммы G; все узлы пронумерованы снизу вверх и слева направо. Внизу добавлены два дополнительных узла под номерами 1 и 2. У этого бесконечного «дерева» есть некоторые весьма интересные математические свойства. Двигаясь по нему справа налево, мы получаем знаменитый ряд чисел Фибоначчи: