Эта странная математика. На краю бесконечности и за ним - [72]

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

В 2007 году в рамках конкурса Big Number Duel[49] в непримиримом поединке за самое большое число сошлись двое философов, старых школьных приятелей – Агустин Райо (он же Мексиканский Множитель) из Массачусетского технологического института и Адам Элга (он же Доктор Зло) из Принстона. Победителем становился тот, кто даст определение самому колоссальному числу. Схватка, в которой обмен остротами и сложнейшая математическая, логическая и философская полемика сочетались с драматизмом боя за звание чемпиона мира по боксу, проходила в забитой до отказа аудитории центра “Стата” МТИ. Первый удар нанес Элга, начертав на доске единицу (видимо, в надежде, что его соперник не в форме). Райо незамедлительно парировал этот выпад, заполнив единицами всю доску. Элга тут же удалил часть линии у основания всех единиц, кроме первых двух, превратив их тем самым в знаки факториала. Так поединок продолжался, постепенно выходя за рамки знакомой математики, пока соперники не стали на ходу изобретать собственную нотацию для все больших чисел. Говорят, что в какой-то момент один из зрителей спросил Элгу: “А это число вообще можно вычислить?” На что тот после краткой паузы ответил: “Нет”. Наконец Райо отправил соперника в нокаут сокрушительным числом, описанным им как “наименьшее положительное число, большее любого конечного положительного числа, которое может быть выражено на языке теории множеств первого порядка с использованием не более чем гугола символов”. Мы не знаем, насколько велико число Райо, и, скорее всего, никогда не узнаем. Ни один компьютер никогда не сумеет его вычислить, даже если бы во Вселенной хватило места для гугола символов. Дело здесь не в нехватке места или времени: число Райо невычислимо, так же как неразрешима проблема остановки.

Афиша конкурса Big Number Duel, проходившего в Массачусетском технологическом институте.

На сегодняшний день, если говорить о более-менее осмысленных больших числах, число Райо – своего рода граница, отделяющая нас от неизвестного. Называли и бо́льшие числа, такие, например, как BIG FOOT, объявленное в 2014 году. Но чтобы получить хотя бы смутное представление о BIG FOOT, нам придется погрузиться в странную область под названием “вселенная куч” (oodleverse) и выучить язык теории куч первого порядка – а здесь не обойтись без ученой степени в области высшей математики и очень своеобразного чувства юмора. Да и в любом случае все самые большие на сегодня числа построены по тому же принципу, что и число Райо.