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

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

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

Ахилл и Черепаха только что доели превосходный ужин на двоих в лучшем китайском ресторане города.

Ахилл: Здорово вы управляетесь с палочками, г-жа Ч.

Черепаха: Приходится — я с детства питаю слабость к восточной кухню. Как насчет вас, Ахилл — вам понравилось?

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

Черепаха: Что ж, с удовольствием побеседую с вами, пока мы пьем чай. Официант! (Подходит официант.) Пожалуйста, принесите наш счет. И еще немного чая! (Официант торопливо уходит.)

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

Черепаха: Боюсь, что нет. Что это такое?

Ахилл: Хайку — это японская поэма, в которой семнадцать слогов. Правильнее сказать, что это мини-поэма, наводящая на размышление так,же, как благоуханный розовый лепесток или покрытые росой кувшинки в пруду. Обычно хайку состоит из группы пяти слогов, затем — семи, и затем — снова пяти.

Черепаха: Такая краткость — всего семнадцать слогов — но где же здесь смысл?

Ахилл: Смысл живет также в голове читателя — не только в хайку.

Черепаха: Гм-м-м… Это утверждение наводит на размышления.

(Подходит официант со счетом, чайничком, полным чая, и парой печений «с сюрпризом» — бумажкой, на которой написана судьба едока.)

Премного благодарна. Еще чайку не желаете, Ахилл?

Ахилл: Пожалуй. Эти печеньица выглядят весьма аппетитно. (Берет печенье, откусывает кусочек и начинает жевать.) Эй — что эта за штуковина тут внутри? Клочок бумаги?

Черепаха: Это ваша судьба, Ахилл. Во многих китайских ресторанах вместе со счетом подают печенья с судьбой-сюрпризом, чтобы смягчить удар. Завсегдатаи китайских ресторанов обычно считают их не за печенья, а за посланцев судьбы. К несчастью, вы, кажется, проглотили кусочек своей судьбы. Что там написано, на оставшемся клочке?

 Ахилл: Странно — все буквы сгрудились в кучу, нет никакого деления на слова. Может быть, это надо расшифровать? О, я понял если расставить промежутки там, где надо, получится: «НИС КЛАДУН ИЛ АДУ». Поистине, адская бессмыслица! Может быть, это что-то вроде хайку, от которого я отъел большинство слогов.

Черепаха: В таком случае, ваша судьба теперь всего лишь 6/17 хайку. Веселенькие ассоциации все это вызывает. Колдуны, болота, черти, клады… Что и говорить, картинка унилая… унылая, я имею в виду. Это звучит как комментарий к новой форме искусства — 6/17 хайку. Можно мне взглянуть?

Ахилл (протягивая Черепахе узкий клочок бумаги): Конечно.

Черепаха: Но, Ахилл, в моей «расшифровке» получается нечто совершенно другое! Это вовсе не 6/17 хайку, а шестисложное послание — и вот что в нем написано «НИ СКЛАДУ НИ ЛАДУ». Поистине, глубокий комментарий к этой новой форме искусства — 6/17 хайку!

Ахилл: Вы правы. Удивительно, что это послание содержит комментарий о самом себе!

Черепаха: Я только передвинула рамку чтения на единицу — сдвинула все промежутки между словами на один интервал.

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

Черепаха (ловко разламывая печенье, читает): «Судьбу едока не печенье содержит, а его рука».

Ахилл: Ваша «судьба» тоже хайку, г-жа Черепаха — по крайней мере, в ней семнадцать слогов. 5-7-5.

Черепаха: Потрясающе! Я бы сама этого ни за что не заметила, Ахилл — такие вещи только вы подмечаете. То, что меня больше всего удивило, это сам текст послания; разумеется, его можно интерпретировать по-разному.

Ахилл: Наверное, мы все интерпретируем послания по-своему, когда с ними сталкиваемся… (Лениво рассматривает чаинки на дне чашки.)

Черепаха: Подлить вам чаю?

Ахилл: Да, спасибо. Кстати, как поживает ваш товарищ, старый Краб? Я частенько о нем вспоминаю, с тех пор, как вы рассказали мне о его диковиной патефонной войне.

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

Ахилл: Расскажите-ка мне об этом поподробнее. Обожаю эти автоматы — кругом разноцветные огоньки, и когда опустишь монетку, машина играет глупые песни, которые так и окунают тебя в старое доброе прошлое…

Черепаха: Этот проигрыватель слишком велик, чтобы держать его дома, и Краб построил для него во дворе специальный навес.

Ахилл: Не представляю себе, почему он такой большой? Может, в нем огромная коллекция пластинок?

Черепаха: На самом деле, в нем всего одна запись.

Ахилл: Что? Проигрыватель-автомат с одной пластинкой? Это уже само по себе противоречие! Почему же он так велик? Может, его единственная пластинка — гигант двадцати футов в диаметре?

Черепаха: Да нет, пластинка самая обыкновенная.

Ахилл: Ах, г-жа Черепаха, не иначе как вы надо мной смеетесь. Ну скажите на милость, что это за автомат с единственной песней?

Черепаха: Кто сказал хотя бы слово о единственной песне?

Ахилл: Любой проигрыватель-автомат, с которым я когда-либо сталкивался, подчинялся фундаментальной аксиоме этих аппаратов: «одна пластинка, одна песня.»

Черепаха: Этот автомат не таков, Ахилл. Единственная пластинка в нем расположена вертикально, и за ней находится небольшая, но сложная система рельсов, на которых подвешены проигрыватели. Когда вы нажимаете на пару кнопок, скажем, В-1, вы выбираете один из проигрывателей. Это пускает в действие механизм, и проигрыватель со скрипом отправляется по ржавым рельсам. Вскоре он прибывает к краю пластинки, и — щелк! — устанавливается в нужную позицию.