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

Черепаха: Мне кажется, я чувствую знакомый запах… Не вытаскин ли это?

Ахилл: И правда… откуда этот запах?

Черепаха: По-моему, это здесь… О! Я нашла целую бутыль! Это он и есть!

Ахилл: Вытаскин! Давайте напьемся с горя!

Черепаха: Надеюсь, что это не протолкин — они до того похожи, что их трудно различить.

Ахилл: Что вы сказали про Толкиена?

Черепаха: Я ничего подобного не говорила. У вас уже галлюцинации начинаются…

Ахилл: Б-батюшки мои! Надеюсь, что нет… Ну что же, поехали!

(И друзья начинают отхлебывать вытаскин (или протолкин?) — и вдруг — ХЛОП! Кажется, это-таки оказался вытаскин…)

Черепаха: Забавная история, ничего не скажешь. Вам понравилось?

Ахилл: Так, ничего себе… Интересно, выбрались ли они в конце концов из ямы страшного Мажотавра? Бедняга Ахилл, он так хотел опять стать большим.

Черепаха: Не беспокойтесь — они выбрались, и Ахилл снова вырос до своих обычных размеров. Вытаскин оказался весьма кстати…

Ахилл: Не знаю, не знаю… Единственное, в чем я сейчас АБСОЛЮТНО уверен, это в том, что нам не мешало бы найти нашу бутылочку с настойкой — у меня уже давно горло пересохло. И ничто так не утоляет жажду, как выталкивающая настойка

Черепаха: Она к тому же известна своим тонизирующим действием. Известны случаи, когда народ просто с ума по ней сходил. Например, когда в начале века продуктовая фабрика Шёнберга перестала производить джин с тоником и начала производство какао, вы не представляете себе, какой из-этого поднялся шум — настоящая какаофония!

Ахилл: Воображаю… Но давайте же искать настойку! Погодите — взгляните-ка на этих ящериц на столе! Не кажется ли вам, что в них есть что-то необычное?

Черепаха: Не вижу ничего особенного. А что такое?

Ахилл: Посмотрите: они вылезают из плоскости картины без помощи выталкивающей настойки! Как они это делают?

Черепаха: Разве я вам не говорила? Вы можете вылезти из картины, двигаясь перпендикулярно ее плоскости. Ящерки научились лезть НАВЕРХ, когда они хотят выбраться из двухмерного мира альбома.

Ахилл: Может быть, мы можем так же выбраться из этой картины Эшера наружу?

Черепаха: Разумеется — нужно только подняться уровнем выше. Хотите попытаться?

Ахилл: Все что угодно, только бы попасть домой! Я уже сыт по горло этими занимательными приключениями.

Черепаха: В таком случае, следуйте за мной наверх.

(И они поднимаются на один уровень.)

Ахилл: Хорошо быть снова у себя дома… Но постойте, здесь что-то не то! Это вовсе не мой дом — это ВАШ дом, г-жа Черепаха!

Черепаха: Вы правы — и я предовольна, так как перспектива тащиться от вас к себе домой мне совершенно не улыбалась. Я прямо-таки валюсь с лап от усталости.

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

Черепаха: Я думаю! Вот это удача так удача!

ГЛАВА V: Рекурсивные структуры и процессы

Что такое рекурсия?

ЧТО ТАКОЕ РЕКУРСИЯ? То, что было проиллюстрировано в диалоге «Маленький гармонический лабиринт»: вложенность схем одна в другую и варианты этой вложенности. Рекурсия — весьма общее понятие. (Рассказы внутри рассказов, фильмы внутри фильмов, картины внутри картин, матрешечки внутри матрешек (даже скобки внутри скобок!) — вот лишь несколько симпатичных примеров.) Однако читатель должен иметь в виду, что в этой главе термин «рекурсия» употребляется в ином значении, чем в главе III, и эти два значения связаны только косвенно. Эта связь должна проясниться к концу главы.

Иногда рекурсия приближается к парадоксу. Например, существуют рекурсивные определения. С первого взгляда может показаться, что в этом случае нечто определяется через себя самоё. Из этого получился бы если не парадокс, то порочный круг и бесконечное возвращение к началу. На самом деле, правильно сформулированное рекурсивное определение никогда не приводит ни к тому, ни к другому. Дело в том, что рекурсивные определения никогда не определяют предметы или идеи через них самих — вместо этого они используют более простые версии определяемого понятия. Чтобы вам стало понятнее, что я имею в виду, приведу несколько примеров рекурсивных определений.

Один из часто встречающихся типов рекурсии в повседневной жизни — это прекращение какого-либо дела на время, с тем, чтобы сделать более простое дело, зачастую того же типа, что и первое. Вот хороший пример. У директора фирмы на столе стоит сложный телефон, по которому ему могут звонить несколько человек одновременно. Директор разговаривает с А; в этот момент звонит Б. Директор спрашивает А, может ли тот подождать минутку. На самом деле, ему совершенно все равно, может ли А подождать, — он просто нажимает кнопку и переключается на разговор с Б. Тут звонит В. Теперь уже и Б приходится подождать. Так может продолжаться до бесконечности — однако не будем увлекаться. Предположим, разговор с В закончился; наш директор «выталкивается» обратно и продолжает беседу с Б. Между тем, на другом конце провода А в раздражении барабанит пальцами по столу и слушает сладенькие мелодии, передающиеся по телефону чтобы скрасить его ожидание… Самый простой случай был бы, если бы звонок Б закончился и директор наконец вернулся бы к А. Но может случиться, что когда он разговаривает с Б, звонит Д. Б снова оказывается «протолкнутым» в стек ждущих своей очереди. По окончанию разговора с Д директор вернется к Б, а затем к А. Разумеется, здесь он действует совершенно механически — я пытаюсь показать рекурсию в самой чистой форме.

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

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

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