Агниджо Банерджи - Эта странная математика. На краю бесконечности и за ним

Как явствует из названия функции [47] От англ. tree – “дерево”. , она напоминает обычное дерево, растущее в лесу, или генеалогическое древо с ветвями, отходящими от общего ствола. Математические деревья – это особая разновидность так называемых графов. Их не нужно путать с графиками. График мы обычно представляем себе как кривую, показывающую соответствие между двумя величинами. Граф же в математике – нечто иное: это способ представления данных, когда точки, называемые узлами или вершинами, соединены отрезками – ребрами. Если, начав с одного из узлов графа и передвигаясь по его ребрам к другим узлам, можно вернуться к исходному, ни разу не проходя ни по одному ребру или узлу дважды, такой маршрут, и сам граф, называется циклом. Если от любого узла можно добраться до любого другого, не проходя дважды ни по одному ребру или узлу, то пройденный маршрут именуют путем, а граф – связным. Деревом называется связный граф, не содержащий циклов. И генеалогические, и биологические деревья имеют именно такую структуру. Если все узлы графа пронумеровать или присвоить им неповторяющиеся цвета, то такое дерево называется помеченным. Если одну из вершин дерева обозначить как корень, то получается корневое дерево. Одно из полезных свойств корневого дерева состоит в том, что от любого его узла можно проследить путь к корню.

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

В ответ на поставленный вопрос американский математик и логик Харви Фридман, занесенный в 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, но состоящей из графов, в которых у каждой вершины не больше трех ребер).