Гёдель, Эшер, Бах. Эта бесконечная гирлянда

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

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

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

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

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

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

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

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

Канон с интервальным увеличением

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

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

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

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

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