Эта странная математика

Некоторые из математических деревьев, имеющих ту же структуру ветвей, что и у реального дерева, можно встроить в другие аналогичные деревья. Их называют “гомеоморфно вложимыми”. На простом языке это означает, что они похожи по форме или виду и одно из них – уменьшенный вариант другого. У математиков, конечно, есть для этого термина более точное определение. Они начинают с большего по размеру дерева и смотрят, как сильно можно “обрезать” его крону, используя два метода. Первый – удаление узлов. Если есть узел (кроме корневого), с которым соединены всего два ребра, его можно удалить, а ведущие к нему ребра срастить в одно. Второй метод – удаление ребер. Если два узла соединены единственным ребром, то это ребро стягивается, а узлы на его концах сливаются в один. Цветом получившегося нового узла становится цвет того из них, который был ближе к корню. Если можно, применяя эти две операции в любом порядке, из большего дерева получить меньшее, то говорят, что меньшее дерево гомеоморфно вложимо в большее. Американский математик и статистик Джозеф Краскал доказал важную теорему, связанную с ними. Предположим, у нас есть ряд деревьев, в котором первое дерево может иметь только один узел, второе – не больше двух узлов, третье – не больше трех и так далее; при этом ни одно не может быть гомеоморфно вложено ни в какое из последующих. Краскал обнаружил, что рано или поздно такая последовательность должна закончиться. Но какой может быть ее максимальная длина?

В ответ на поставленный вопрос американский математик и логик Харви Фридман, занесенный в 1967 году в “Книгу рекордов Гиннесса” как самый молодой университетский преподаватель в мире (в Стэнфорде в возрасте 18 лет), определил “функцию дерева” TREE(n) в качестве максимальной длины такой последовательности, где n – количество цветов для вершин. Фридман изучил выходные значения функции для различных значений n. Первое дерево состоит из единственного узла, имеющего определенный цвет, который нельзя использовать снова. Если n = 1, то этот цвет – единственный и последовательность тут же завершается, а значит, TREE(1) = 1. Если n = 2, у нас есть еще один цвет. Второе дерево может иметь до двух узлов включительно, так что содержит два узла, окрашенных в этот второй цвет. Третье дерево также должно содержать только этот цвет, но может иметь только один узел, поскольку иначе второе дерево будет гомеоморфно вложимо в третье. Больше в этом случае деревьев быть не может, поэтому TREE(2) = 3. И вот мы дошли до TREE(3) – и тут, как обнаружил Фридман, происходит нечто невероятное, настоящий взрыв. Совершив гигантский скачок, количество узлов внезапно вырастает до размеров, намного превышающих число Грэма, и достигает в быстрорастущей иерархии малого ординала Веблена – совсем не малого числа, которое мы уже упоминали, путешествуя по различным бесконечностям.

Гугология – поиск новых способов определения все бо́льших и бо́льших чисел – стала настолько популярной, что в этой области уже проводятся конкурсы. Один из первых, Bignum Bakeoff[48], организовал в 2001 году американский вундеркинд Дэвид Мейз. Перед участниками стояла задача написать на языке C программу не длиннее 512 символов (не считая пробелов), возвращающую как можно большее число. Поскольку для реального выполнения поданных на конкурс программ современным компьютерам понадобилось бы больше времени, чем существует Вселенная, код анализировали вручную, а победителя определяли на основании позиции в быстрорастущей иерархии. Первое место заняла программа loader.c, названная именем ее автора Ральфа Лоудера из Новой Зеландии. Для вычисления окончательного результата потребовались бы невероятно долгое время и машина с чудовищным объемом памяти. Но если бы это все же было возможно, то полученное число Лоудера затмило бы собой и TREE(3), и некоторых других героических обитателей гугологического космоса: таких, например, как SCG(13) – тринадцатый элемент последовательности, именуемой “числа субкубических графов” (схожей с последовательностью TREE, но состоящей из графов, в которых у каждой вершины не больше трех ребер).