Возьмем для примера функцию fω + 1(2). Согласно нашему рекурсивному правилу, она равносильна fω(fω(2)). Раз мы определили fω(2) как fn(2), то можем записать fω + 1(2) как fω(f2(2)), просто заменив внутреннюю ω на 2. (Узнать значение внешней fω нельзя до тех пор, пока нам не будет известно, какое значение примет внутренняя.) Поскольку f2(2) = 8, от fω + 1(2) у нас остается fω(8). Наконец, мы можем упростить внешнюю ω и получить f8(8), включающую в себя семь стрелок. Этот пример, хоть и показывает, как можно использовать функцию fω + 1 для применения рекурсии к количеству стрелок, не дает полного представления о внушительных возможностях этой функции. Они становятся очевидными только по мере роста n и числа соответствующих ему петель обратной связи. При n = 64 получаем fω + 1(64), что приблизительно равно числу Грэма. Следующая ступенька быстрорастущей иерархии, fω + 2(n), открывает принципиально новые горизонты: на этом этапе весь математический аппарат, послуживший нам для достижения числа Грэма, подставляется сам в себя. В результате получается число, которое можно приближенно записать как gg … 64 (с 64 уровнями g в подстрочном индексе), но хотя бы отдаленно представить себе его масштаб не стоит даже пытаться.
Счетно-бесконечные ординалы простираются насколько хватает глаз, и каждый последующий из них – основа для новой, более мощной рекурсивной функции, оставляющей далеко позади предыдущую. Одни омеги составляют ряд такой длины, что он заканчивается только на омеге, возведенной в степенную башню высотой в омегу омег. Этот могучий ординал – эпсилон-ноль – настолько велик, что его невозможно описать средствами нашей классической арифметики, называемой арифметикой Пеано. С каждым шагом вдоль нескончаемой дороги омег конечное число, получаемое путем применения рекурсии, увеличивается на непостижимую величину. Но за самой величественной степенной башней из омег высятся башни, сложенные из многочисленных ярусов еще более внушительных бесконечных ординалов: сначала эпсилонов, потом дзет и так далее, и несть им числа – как мы уже выяснили раньше, когда говорили о бесконечности. С постоянным ростом ординалов растет и эффект обратной связи. И вот наконец мы добрались до умопомрачительно большого ординала гамма-ноль (Γ0), у которого есть и более звучное название: ординал Фефермана – Шютте, в честь впервые описавших его американского философа и логика Соломона Фефермана и немецкого математика Карла Шютте. Несмотря на то, что гамма-ноль – все еще счетный ординал и есть после него и другие, определить его можно, только используя несчетные ординалы (то есть такие, которые невозможно получить путем перестановки элементов алеф-нуля; для несчетных ординалов требуется алеф-один или больше элементов). Этот процесс напоминает ход развития само2й быстрорастущей иерархии. Как для описания громадных конечных чисел нам пришлось в быстрорастущей иерархии прибегнуть к бесконечным ординалам, так и для описания огромных счетно-бесконечных ординалов мы вынуждены обратиться к ординалам несчетным. В языке просто не существует эпитетов, способных адекватно описать величину конечных чисел, которые можно получить с помощью рекурсии, используя ординал Фефермана – Шютте и другие, следующие за ним. Ни один математик, будь он хоть семи пядей во лбу, не в силах постичь всю безмерность чисел, порождаемых рекурсивными методами. Что, впрочем, нисколько не мешает математикам изобретать все более и более эффективные способы, генерирующие большие числа. Один из самых примечательных методов – функция TREE.
Как явствует из названия функции
[47], она напоминает обычное дерево, растущее в лесу, или генеалогическое древо с ветвями, отходящими от общего ствола. Математические деревья – это особая разновидность так называемых графов. Их не нужно путать с графиками. График мы обычно представляем себе как кривую, показывающую соответствие между двумя величинами. Граф же в математике – нечто иное: это способ представления данных, когда точки, называемые узлами или вершинами, соединены отрезками – ребрами. Если, начав с одного из узлов графа и передвигаясь по его ребрам к другим узлам, можно вернуться к исходному, ни разу не проходя ни по одному ребру или узлу дважды, такой маршрут, и сам граф, называется циклом. Если от любого узла можно добраться до любого другого, не проходя дважды ни по одному ребру или узлу, то пройденный маршрут именуют путем, а граф – связным. Деревом называется связный граф, не содержащий циклов. И генеалогические, и биологические деревья имеют именно такую структуру. Если все узлы графа пронумеровать или присвоить им неповторяющиеся цвета, то такое дерево называется помеченным. Если одну из вершин дерева обозначить как корень, то получается корневое дерево. Одно из полезных свойств корневого дерева состоит в том, что от любого его узла можно проследить путь к корню.
Некоторые из математических деревьев, имеющих ту же структуру ветвей, что и у реального дерева, можно встроить в другие аналогичные деревья. Их называют “гомеоморфно вложимыми”. На простом языке это означает, что они похожи по форме или виду и одно из них – уменьшенный вариант другого. У математиков, конечно, есть для этого термина более точное определение. Они начинают с большего по размеру дерева и смотрят, как сильно можно “обрезать” его крону, используя два метода. Первый – удаление узлов. Если есть узел (кроме корневого), с которым соединены всего два ребра, его можно удалить, а ведущие к нему ребра срастить в одно. Второй метод – удаление ребер. Если два узла соединены единственным ребром, то это ребро стягивается, а узлы на его концах сливаются в один. Цветом получившегося нового узла становится цвет того из них, который был ближе к корню. Если можно, применяя эти две операции в любом порядке, из большего дерева получить меньшее, то говорят, что меньшее дерево гомеоморфно вложимо в большее. Американский математик и статистик Джозеф Краскал доказал важную теорему, связанную с ними. Предположим, у нас есть ряд деревьев, в котором первое дерево может иметь только один узел, второе – не больше двух узлов, третье – не больше трех и так далее; при этом ни одно не может быть гомеоморфно вложено ни в какое из последующих. Краскал обнаружил, что рано или поздно такая последовательность должна закончиться. Но какой может быть ее максимальная длина?
В ответ на поставленный вопрос американский математик и логик Харви Фридман, занесенный в 1967 году в “Книгу рекордов Гиннесса” как самый молодой университетский преподаватель в мире (в Стэнфорде в возрасте 18 лет), определил “функцию дерева” TREE(n) в качестве максимальной длины такой последовательности, где n – количество цветов для вершин. Фридман изучил выходные значения функции для различных значений n. Первое дерево состоит из единственного узла, имеющего определенный цвет, который нельзя использовать снова. Если n = 1, то этот цвет – единственный и последовательность тут же завершается, а значит, TREE(1) = 1. Если n = 2, у нас есть еще один цвет. Второе дерево может иметь до двух узлов включительно, так что содержит два узла, окрашенных в этот второй цвет. Третье дерево также должно содержать только этот цвет, но может иметь только один узел, поскольку иначе второе дерево будет гомеоморфно вложимо в третье. Больше в этом случае деревьев быть не может, поэтому TREE(2) = 3. И вот мы дошли до TREE(3) – и тут, как обнаружил Фридман, происходит нечто невероятное, настоящий взрыв. Совершив гигантский скачок, количество узлов внезапно вырастает до размеров, намного превышающих число Грэма, и достигает в быстрорастущей иерархии малого ординала Веблена – совсем не малого числа, которое мы уже упоминали, путешествуя по различным бесконечностям.
