Самое большое число
Проблема с целыми числами в том, что мы изучили лишь самые маленькие из них.
Возможно, все самое интересное происходит там, где числа очень большие – настолько большие,
что мы просто не в состоянии их себе представить.
Рональд Грэм
Попросите ребенка назвать самое-самое большое число – и, скорее всего, услышите в ответ что-то вроде “пятьдесят тысяч миллионов миллиардов триллионов триллионов…” и так далее, пока объект расспросов не устанет нанизывать одно на другое реальные числа вперемешку с “сиксиллионами” и “мультиллиардами”. По житейским меркам это и вправду очень большие числа, может быть, даже превышающие количество всех живых существ на Земле или звезд во Вселенной. Но по сравнению с умопомрачительно гигантскими числами, которые способны конструировать математики, – просто детские шалости. Если бы вам вдруг взбрело в голову провести остаток своей сознательной жизни, произнося “триллион триллионов триллионов триллионов…” и так далее со скоростью один “триллион” в секунду, то получившееся в итоге число было бы просто мизерным по сравнению с монстрами числового космоса, с такими как число Грэма, TREE(3) и поистине исполинское число Райо.
Известно, что одним из первых систематически начал задумываться об очень больших числах Архимед. Он родился в Сиракузах на острове Сицилия около 287 года до нашей эры и считается величайшим математиком древности и одним из самых великих в истории человечества. Он задался вопросом: сколько всего на свете песчинок и сколько вообще их можно вместить в целый мир, который, как считали древние греки, простирается до сферы “неподвижных звезд” (так, в отличие от планет, они называли звезды, видимые на ночном небе). Его трактат “Исчисление песчинок” начинается так:
Некоторые люди полагают, государь Гелон, что число песка по величине бесконечно; я говорю не только о песке, который имеется в окрестностях Сиракуз и остальной Сицилии, но и о том, который имеется во всех странах, как населенных, так и не населенных. Есть, однако, и такие, которые не считают его бесконечным, но тем не менее думают, что не существует такого имеющего название числа, которое было бы больше его количества.
Архимед, считавший, что “математика… открывает свои тайны только тому, кто приближается к ней с чистой любовью, ради ее собственной красоты”.
Чтобы подготовить почву для своих расчетов космического масштаба, Архимед взялся для начала расширить существовавшую в то время систему наименования больших чисел – а это основная проблема, с которой сталкивались с тех пор все математики, пытавшиеся описывать все бо́льшие и бо́льшие целые числа. Греки называли число 10 000 “мюриас”, что подразумевает неисчислимость. У римлян же оно называлось “мириадой”. В качестве точки отсчета на пути в мир огромных чисел Архимед использовал “мириаду мириад”, то есть 100 000 000, или, если использовать современное экспоненциальное представление, 108. Число это намного превышало любое, для какого у греков нашлось бы практическое применение. Все числа, идущие до мириады мириад, Архимед назвал “первыми”. Те, что шли вплоть до мириады мириад, помноженной на мириаду мириад (то есть до единицы с 16 нулями, или 1016), он отнес ко “вторым”; потом перешел к “третьим”, “четвертым” и так далее, причем каждый последующий разряд в его схеме был в мириаду мириад раз больше предыдущего. В конце концов он достиг “мириад-мириадного” разряда, то есть числа 108, умноженного само на себя 108 раз (или 108 в степени 108). Таким порядком Архимеду удалось описать числа длиной вплоть до 800 000 000 знаков. Их он отнес к “числам первого периода”. Само число 10800 000 000 он принял за начало второго периода, после чего повторил весь процесс снова. Для второго периода Архимед применил ту же методику, что и для первого, увеличивая каждый последующий разряд в мириаду мириад раз до тех пор, пока в конце мириад-мириадного периода не достиг колоссального числа 1080 000 000 000 000 000, или мириады мириад, возведенной в степень, равную мириаде мириад, умноженной на мириаду мириад.
Как выяснилось позже, для того чтобы реализовать свой проект по подсчету песчинок, Архимед мог ограничиться и первым периодом. Согласно тогдашним представлениям о космосе, весь мир вплоть до неподвижных звезд имел объем шара с диаметром в два световых года, в центре которого находилось Солнце. Оценив размер песчинки, Архимед пришел к следующему выводу: чтобы превратить космос в гигантский песчаный пляж, потребуется 8 × 1063 песчинок, то есть всего-навсего число восьмого разряда первого периода. Даже если взять рассчитанный современными учеными диаметр наблюдаемой Вселенной – 92 миллиарда световых лет, – ее объем не сможет вместить больше 1095 песчинок, а это все равно число лишь двенадцатого разряда первого периода.
Возможно, в западном мире Архимед и был чемпионом по большим числам, но ученые мужи Востока в поисках числовых тяжеловесов уже скоро побьют все его рекорды. В написанном на санскрите индийском тексте приблизительно III века “Лалитавистара” Будда Гаутама описывает математику по имени Арджуна систему счисления, начинающуюся с “коти” – 10 000 000 на санскрите. После коти идет длинный перечень имеющих собственные названия чисел, каждое из которых в 100 раз больше предыдущего: 100 коти называются “аюта”, 100 аюта называются “ниюта”, и так далее, до числа “таллакшана”, представляющего собой единицу с 53 нулями. Он называет и бо́льшие числа, такие как “дхваджагравати”, равное 1099, вплоть до гиганта “уттарапараманураджаправеша” – 10421.
Другой буддийский текст идет еще дальше по пути к исполинским, чудовищно большим числам. В “Аватамсака сутре” описан целый космос, состоящий из бесконечного множества взаимопроникающих уровней. В тридцатой главе Будда вновь пространно рассуждает о больших числах начиная с 1010, после чего возводит его в квадрат, получая 1020, снова возводит в квадрат, получая 1040, и продолжает дальше, последовательно переходя к 1080, 10160, 10320, пока не достигает числа 10101 493 392 610 318 652 755 325 638 410 240. Возведите его в квадрат, провозглашает Будда, и результат будет “неисчислимым”. Однако и на этом он не останавливается. Вслед за “неисчислимым” (очевидно, основательно поработав с санскритским словарем в поисках достойных эпитетов) он продолжает перечислять все бо́льшие и бо́льшие числа, называя их “безмерным”, “безграничным”, “несравнимым”, “бессчетным”, “непостижимым”, “немыслимым”, “неизмеримым” и “неизъяснимым”, завершая всю эту пирамиду “невыразимым”, которое, как показывают расчеты, равно 1010×(2^122) (значок ^ используется, чтобы показать, что одно число возводится в степень другого; таким образом, 1010×(2^122) – это то же, что и 1010×(2 в 122-й степени)). Рядом с “невыразимым” самое большое число из упомянутых в трудах Архимеда, 1080 000 000 000 000 000, кажется просто карликом. Чтобы оно попало хотя бы в ту же весовую категорию, его пришлось бы возвести в степень, примерно равную 66 000 000 000 000 000 000.
И Архимеду, и авторам буддийских сутр большие числа нужны были для того, чтобы дать представление о громадности вселенной в их понимании. Буддисты, кроме того, считали, что, дав чему-либо название, человек приобретает над этим определенную власть. Но математиков, как правило, мало интересует бесцельное изобретение новых схем для наименования и обозначения все возрастающих больших чисел. Наша система, в которой для наименования больших чисел используются слова, заканчивающиеся на “-иллион”, восходит к французскому математику XV века Никола Шюке. В своем трактате Le Triparty en la Science des Nombres (“Наука о числах в трех частях”) он записал огромное число, разбил его на группы по шесть знаков в каждой и предложил назвать эти группы так:
…миллион, вторая отметка – биллион, третья отметка – триллион, четвертая – квадриллион, пятая – квииллион, шестая – сикслион, седьмая – септиллион, восьмая – оттиллион, девятая – нониллион, и далее так же поступать с другими числами столь долго, сколько будет угодно.
В 1920 году американский математик Эдвард Казнер попросил своего девятилетнего племянника Милтона Сиротту придумать название для числа, изображаемого единицей со ста нулями. Предложенное мальчишкой название “гугол” приобрело всеобщую известность после того, как Казнер написал о нем в своей книге “Математика и воображение” (Mathematics and the Imagination), созданной в соавторстве с Джеймсом Ньюменом. Помимо гугола юный Сиротта также предложил название “гуголплекс” для числа, записываемого как “единица со шлейфом из стольких нулей, сколько сможешь написать, пока не устанешь”. Казнер решил дать числу более точное определение, поскольку “кто-то может устать раньше, кто-то позже, и не годится, чтобы Карнеру [чемпиона по боксу в тяжелом весе] считали более сильным математиком, чем доктора Эйнштейна, просто потому, что он выносливее физически”. Впрочем, слово “усталость” (и это еще мягко сказано) – довольно точное описание того, что ощутит человек, которому придет в голову написать число гуголплекс. Судите сами: согласно определению Казнера, гуголплекс – это 10гугол, или единица с гуголом нулей. Число гугол нетрудно записать полностью:
10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
Но гуголплекс неизмеримо больше. На всей планете не хватит бумаги, да что там бумаги на Земле, во всей видимой Вселенной не хватит вещества, чтобы записать все знаки гуголплекса, даже если изображать нули размером с протоны или электроны. Гуголплекс намного больше самого огромного из чисел, каким ученые древности дали названия, включая великанское “невыразимое”. И все же он не так велик, как число, которое получил в 1933 году математик из ЮАР Стэнли Скьюз, работая над проблемой в области простых чисел. Названное в честь этого ученого, число Скьюза представляет собой максимально возможное значение (верхний предел), которое получается при решении математической задачи, связанной с распределением простых чисел. Знаменитый британский математик Годфри Харолд Харди, наставник Рамануджана и автор популярной “Апологии математика”, назвал его на тот момент “самым большим числом, когда-либо использованным в математике для какой-либо конкретной цели”. Его значение – 1010^10^34, или, если точнее, 1010^8852142197543270606106100452735038,55. Для того чтобы рассчитать этот колоссальный по величине верхний предел, Скьюзу пришлось исходить из предположения о справедливости гипотезы Римана, над которой математики до сих пор ломают голову. Два десятилетия спустя он объявил, что рассчитал еще одно число, в связи с той же задачей, но на этот раз не прибегая к предположению о верности гипотезы Римана. Оно получилось еще больше – 1010^10^964 плюс-минус несколько триллионов.
От чистой математики не отставала и физика со своими головоломными проблемами, решение которых также время от времени приводило к появлению гигантских чисел. На этом фронте одним из первых стал французский математик, физик-теоретик и ученый-энциклопедист Анри Пуанкаре, среди многочисленных трудов которого – исследования того, сколько времени требуется физической системе, чтобы вернуться в определенное исходное состояние. Когда речь идет о вселенной, так называемое время возвращения Пуанкаре – это промежуток времени, необходимый для того, чтобы вещество и энергия, пройдя через немыслимое количество преобразований, перераспределились до состояния, которое в точности, вплоть до субатомного уровня, повторяет начальное. По оценке канадского теоретика Дона Пейджа, в прошлом аспиранта Стивена Хокинга, для наблюдаемой Вселенной время возвращения Пуанкаре составляет 1010^10^10^2,08 лет. Это число больше гуголплекса и находится где-то посередине между малым и большим числами Скьюза. Пейдж также рассчитал максимальное время возвращения Пуанкаре для любой вселенной определенного типа. Оно еще больше – 1010^10^10^10^1,1 лет, что превосходит и второе из чисел Скьюза. Что касается самого гуголплекса, Пейдж отметил, что тот приближенно равен количеству микросостояний в черной дыре, сравнимой по массе с галактикой Андромеды.
И “невыразимое”, и гуголплекс, и числа Скьюза титанически велики для постижения разумом. Но они и рядом не стояли с числом, названным в честь американского математика Рональда Грэма, впервые описавшего его в своей статье 1977 года. Так же как и числа Скьюза, число Грэма – результат работы над серьезной математической проблемой, на этот раз связанной с теорией Рамсея. Приближаться к числу Грэма нам придется постепенно, подобно альпинистам, покоряющим высочайшие вершины мира. Первым шагом будет знакомство с особым способом записи больших чисел, изобретенным американским ученым в области информатики Дональдом Кнутом и известным как стрелочная нотация. Она основана на том факте, что умножение всегда можно представить как многократное сложение, а возведение в степень – как многократное умножение. Например, 3 × 4 – это то же самое, что 3 + 3 + 3 + 3, а 34 = 3 × 3 × 3 × 3. В нотации Кнута возведение в степень обозначается одиночной стрелкой, направленной вверх: например, гугол, или 10100, записывается как 10↑100, а три в кубе, или 33, – как 3↑3. Повторное возведение в степень, для которого нет специального стандартного обозначения, записывается в виде двух стрелок: таким образом, 3↑↑3 = 33^3. Операция ↑↑, называемая тетрацией (поскольку она идет четвертой в иерархии после сложения, умножения и возведения в степень), – штука гораздо более сильная, чем может показаться на первый взгляд. 3↑↑3 = 33^3 = 327, что равно 7 625 597 484 987.
Тетрацию можно представить и в виде степенной башни (кошмар любого наборщика). Если с числом a требуется произвести операцию тетрации порядка k, это записывается следующим образом:
Иначе говоря, число a возводится в степень, представленную башней высотой в k – 1 этаж.
Темп, с которым растет результат математического действия при добавлении новых стрелок, просто ошеломляет: если 3 × 3 = 9, то 3↑3 дает 27, а 3↑↑3 уже больше 7,6 триллиона (13-значное число). Результат тетрации числа 4 еще поразительнее: 4↑↑4 = 4↑4↑4↑4 = 4↑4↑256, что приблизительно равно 10↑10↑154 – то есть больше гуголплекса (10↑10↑100). Перевалить за это огромное число нам удалось с помощью всего-то одной четверки и нескольких простых значков.
Но раз мы сделали такой гигантский шаг, перейдя от простого возведения в степень к тетрации, то, наверное, если добавить еще одну стрелку, можно получить что-то еще более впечатляющее? Что ж, интуиция нас не обманывает. При повторной тетрации, называемой пентацией, результат вырастает так, что аж дух захватывает! Ничем не примечательная запись 3↑↑↑3 – это то же, что 3↑↑3↑↑3, что, в свою очередь, равно 3↑↑7 625 597 484 987, или 3↑3↑3↑3…↑3, – а это уже степенная башня высотой в 7 625 597 484 987 троек. Если башни в 4 этажа достаточно, чтобы получить число, превышающее гуголплекс, только представьте себе, что получится в этом случае. Это невообразимо большое число: человеческой жизни не хватит, чтобы записать его даже в виде степенной башни. В напечатанном виде такая башня дотянется до самого Солнца. Это число, известное как “тритри”, значительно больше любого из тех, что мы упоминали до сих пор; осмыслить его нам, простым смертным, почти невозможно. А ведь мы еще только начали. Тритри, при всей своей величине, – ничтожная песчинка рядом с величественным пиком, который представляет собой число Грэма. Добавив еще одну стрелку, получим 3↑↑↑↑3 = 3↑↑↑3↑↑↑3 = 3↑↑↑тритри.
Давайте разберемся, что это значит. В нагромождении степенных башен самая первая у нас 3; вторая – 3↑3↑3, или 7 625 597 484 987; третья – 3↑3↑3↑3…↑3 c 7 625 597 484 987 тройками, то есть тритри; четвертая – 3↑3↑3↑3…↑3, где тритри троек; и так далее. 3↑↑↑↑3 – это башня под номером тритри. Добавив к трем стрелкам еще одну, мы шагнули на гигантское расстояние, так далеко, что уму непостижимо. А пришли всего лишь к g1 – самому первому из серии чисел g, необходимых для того, чтобы добраться до вершины, то есть до самого числа Грэма. После передышки в базовом лагере g1 продолжаем подъем до следующего лагеря, g2. Помните, что, добавляя в запись числа всего одну стрелку, мы каждый раз увеличиваем его на чудовищную величину. Теперь внимание! Число g2 – это 3↑↑↑↑…↑3 с количеством стрелок, равным g1. Даже робкая попытка осмыслить его масштаб, понять, насколько грандиозными могут быть числа, вызывает головокружение. Всего одна дополнительная стрелка увеличивает результат на феноменальную величину, а в числе g2 таких стрелок g1. В числе g3, как вы уже наверняка догадались, g2 стрелок, в числе g4 – g3 стрелок и так далее. А само число Грэма, G, – это g64. В 1980 году оно было занесено в “Книгу рекордов Гиннесса” как самое большое число, когда-либо использованное в математическом доказательстве.
Математическую проблему, из которой родилось число Грэма, фантастически сложно решить, но довольно легко сформулировать. Связана она с многомерными кубами, то есть n-мерными гиперкубами. Представьте, что все вершины такого куба попарно соединены друг с другом отрезками, окрашенными либо в красный, либо в синий цвет. Грэм задался следующим вопросом: каково наименьшее значение n, при котором для любого варианта окрашивания найдутся четыре вершины, лежащие в одной плоскости и попарно соединенные отрезками одного цвета? Ему удалось доказать, что нижний предел для числа n – 6, а верхний – g64. Этот колоссальный разрыв свидетельствует о сложности задачи. Грэм смог доказать, что значение n, удовлетворяющее ее условиям, существует, но для этого ему пришлось определить верхний предел n с помощью числа умопомрачительной величины. С тех пор математики сумели сократить разрыв до более скромного (по сравнению с первоначальным) диапазона значений n: от 13 до 9↑↑↑4.
Число Грэма, наряду с гуголом и гуголплексом, часто приводят в качестве примера очень большого числа, имея о нем, однако, весьма смутное понятие. Во-первых, это уже далеко не самое большое из описанных чисел. Во-вторых, если уж искать новые “рекордные” числа и способы их представления и описания, то брать за основу число Грэма и увеличивать его с помощью традиционных математических операций не имеет никакого смысла.
В последние годы возник целый раздел занимательной математики под названием “гугология”, посвященный исключительно расширению горизонтов больших чисел путем описания и наименования еще бо́льших экземпляров. В принципе, назвать число, большее любого другого, может кто угодно. Если я назову число Грэма, вы можете сказать “число Грэма плюс 1”, или “число Грэма в степени, равной числу Грэма”, или даже “g64↑↑↑↑…↑g64 c числом стрелок, равным g64” (что примерно равно g65). Но такое “надстраивание” за счет повторного использования одних и тех же математических действий не влечет за собой никаких коренных изменений: в результате все равно получится некая производная числа Грэма. Иначе говоря, придуманное вами число будет построено примерно таким же способом, как и само число Грэма, с помощью аналогичных приемов. Серьезные гугологи называют такую неэлегантную мешанину из уже существующих чисел и функций, никак не затрагивающую исходное большое число по сути, “салатом” и относятся к ней крайне неодобрительно. Число Грэма – это стрелочная нотация, доведенная до предела своих возможностей. В “салате” же к числу Грэма просто применяют какое-нибудь несущественное математическое действие. Такие безыскусные игры со скромным приращением готовых чисел не для гугологов; их интересует разработка принципиально новой системы, которую можно было бы расширить до таких масштабов, чтобы число Грэма показалось пренебрежимо малым. Одна такая бесконечно масштабируемая система уже существует. Она называется быстрорастущей иерархией, поскольку позволяет достичь феноменальных темпов роста. Что еще важнее, эта методика уже опробована математиками на практике и часто используется как эталон при разработке новых способов получения фантастически больших чисел.
Прежде чем говорить о быстрорастущей иерархии, нужно усвоить две вещи. Первое: она представляет собой ряд функций. Функция в математике – это просто соответствие, некое правило, превращающее одно значение, входное, в другое, выходное. Функцию можно представить себе как машинку, которая преобразует одни значения в другие, применяя к ним всегда единый набор действий, например, прибавляя тройку. Если обозначить входное значение буквой x, а функцию записать как f(x) (это произносится как “f от x”), то f(x) = x + 3.
Второе, что нужно знать о быстрорастущей иерархии: в качестве индекса функции (показывающего, сколько раз следует выполнить нужный набор действий) используются порядковые числа – ординалы. Ординалы указывают на положение того или иного объекта в списке или на порядок расположения элементов в ряду. Они могут быть конечными и бесконечными. С конечными порядковыми числами знакомы все: “пятый”, “восьмой”, “сто двадцать третий” и так далее. А вот бесконечные не на слуху, про них знают лишь те, кто интересуется математикой поглубже. Оказывается, и конечные, и бесконечные ординалы – чрезвычайно полезная штука, когда стоит задача добраться до сверхбольших (но все же конечных) чисел и описать их. Индексирование функций с помощью конечных ординалов позволяет дотянуться до вполне солидных больших чисел. Но когда к делу подключаются бесконечные ординалы, когда именно они начинают определять, сколько раз необходимо выполнить функцию, – вот тут быстрорастущая иерархия проявляет себя в полную силу.
С первой ступенькой иерархии все очень просто: это функция, которая всего-навсего прибавляет к числу единицу. Назовем такую начальную функцию f0. Предположим, мы хотим пропустить через жернова нашей функции число n. Тогда f0(n) = n + 1. Но такими крохотными шажками, прибавляя каждый раз по единице, мы не скоро доберемся до больших чисел, поэтому перейдем к функции f1(n). Она берет предыдущую функцию и подставляет ее саму в себя n раз: другими словами, f1(n) = f0(f0(… f0(n))) = = n + 1 + 1 + 1 + … + 1, где в общей сложности n единиц, что дает в итоге 2n. И опять-таки не слишком впечатляет – такими темпами нам долго добираться до страны больших чисел. Но зато эта функция наглядно демонстрирует процесс, из которого быстрорастущая иерархия черпает свою невероятную мощь. И процесс тот – рекурсия.
Искусство, музыка, язык, вычислительные системы, математика – рекурсия встречается во всех этих областях; она многолика, но это всегда нечто, что возвращается к самому себе. Иногда в результате получается просто бесконечно повторяющаяся петля. Возьмите, к примеру, шуточную словарную статью: “Рекурсия. См. рекурсия”. Более детально проработана рекурсивная петля в литографии Маурица Эшера “Картинная галерея” (1956 года), на которой изображено здание городской галереи, в которой выставлена картина, изображающая здание галереи, в которой… и так далее. Классический пример рекурсии в технике – обратная связь, когда выходной сигнал системы подается на ее вход. С этой проблемой нередко приходится сталкиваться, например, рок-музыкантам, если микрофон на сцене расположен перед акустической системой, к которой он подключен. Звук, принимаемый микрофоном, усиливается и подается на динамик системы, откуда вновь поступает на микрофон, и так продолжается до тех пор, пока – довольно скоро – из-за усиления при каждом прохождении цикла звук не превратится в знакомый пронзительный свист. Рекурсия в математике работает примерно так же, только вместо электронной системы “микрофон – усилитель – динамик” здесь функция, которая обращается к самой себе, так что ее выходное значение подается опять на вход.
Итак, мы достигли ступеньки f1(n) на лестнице быстрорастущей иерархии. Следующая ступенька, f2(n), подставляет функцию f1(n) саму в себя n раз. Ее можно записать как f2(n) = f1(f1(… f1(n))) = n × 2 × 2 × 2 × … × 2, где количество двоек равно n. Это то же самое, что n × 2n, где 2n – показательная функция. Если подставить вместо n, скажем, 100, то мы получим f2(100) = 100 × 2100 = = 126 765 060 022 822 940 149 670 320 537 600, или приблизительно 127 миллиардов миллиардов триллионов. Будь это сумма на банковском счете, такое состояние даже Биллу Гейтсу могло бы только во сне присниться, а ведь она гораздо меньше, чем некоторые из известных чисел, что нам уже встречались, таких как гугол. Меньше она и суммы самого крупного в истории иска о компенсации ущерба. Иск на 2 ундециллиона (то есть два триллиона триллионов триллионов) долларов был подан 11 апреля 2014 года жителем Манхэттена Энтоном Пьюрисимой, утверждавшим, что в городском автобусе его покусала “больная бешенством” собака. В бессвязном исковом заявлении на 22 страницы, написанном от руки, к которому была приложена фотография несуразно огромной повязки на среднем пальце, Пьюрисима требовал от управления городского транспорта Нью-Йорка, аэропорта Ла-Гуардия, кафе Au Bon Pain (где его якобы регулярно обсчитывали при покупке кофе), университетского медицинского центра города Хобокена и сотен других организаций выплаты компенсации на общую сумму, превышающую всю денежную массу на планете. В мае 2017 года иск был отклонен “за недостаточностью правовых и фактических оснований”. Будем надеяться, что познания Пьюрисимы в математике не распространяются на быстрорастущую иерархию – иначе за этим иском могут последовать другие, на еще бо́льшие суммы (раньше он уже подавал в суд на несколько крупных банков, Международный музыкальный фонд Лан Лана и Китайскую Народную Республику).
Функция f3(n) представляет собой n повторений функции f2(n), а получающееся в результате число чуть превышает 2 в степени n в степени n в степени n… со степенной башней высотой в n этажей. Это этап двух стрелок, или тетрации, – операции, что мы встречали на подступах к числу Грэма. Дальше продолжаем в том же духе: f4(n) – это три стрелки, f5(n) – четыре стрелки и так далее; то есть каждое увеличение ординала на единицу равносильно добавлению очередной стрелки и еще одному шагу к количеству стрелок n – 1. Это дает уже реально большие числа – не только по повседневным меркам, но даже по меркам сутяжника Пьюрисимы. Однако, если добавлять всего по одной стрелке за раз, даже до числа Грэма не скоро доберешься, не говоря уже о других, гораздо более солидных экземплярах. Здесь нужно какое-то неожиданное решение. Чтобы получить действительно колоссальные конечные числа, нам придется прибегнуть к помощи чисел бесконечных.
Самая маленькая из бесконечностей – это алеф-ноль, бесконечность натуральных чисел. Меняться по величине, то есть по количеству того, что в нем содержится, алеф-ноль не может, зато может меняться по длине – в зависимости от того, как его содержимое организовано. Самая маленькая длина алеф-нуля обозначается бесконечным ординалом омега (ω). Следующая – ω + 1, за ней ω + 2, потом ω + 3 и так далее, без конца. Эти бесконечные ординалы – они называются счетными, потому что их можно расставить по порядку, пронумеровать, – служат нам своего рода трамплином для прыжка в мир самых больших из когда-либо описанных конечных чисел. Для начала нам нужно определить, что подразумевается под функцией fω(n), где в качестве индекса стоит наименьший из бесконечных ординалов. Просто отнять 1 и применить рекурсию, о которой мы говорили выше, здесь не получится, поскольку такого понятия, как ω – 1, не существует. Вместо этого мы определяем fω(n) как fn(n). Заметьте, это не значит, что ω = n. Мы просто выражаем fω(n) через (конечные) ординалы, меньшие ω, чтобы привести функцию к виду, удобному для вычислений. Вы, возможно, возразите и скажете, что с таким же успехом можно просто написать fn(n) вместо fω(n) и получить тот же результат; но тогда нам не удастся сделать следующий шаг – а именно он является решающим и позволяет раскрыть весь невероятный потенциал, заложенный в быстрорастущей иерархии. Как только мы переходим от fω(n) к fω+1(n), происходит нечто качественно новое. Мы помним, что, увеличивая на единицу ординал, стоящий в индексе функции, мы подставляем предыдущую функцию саму в себя n раз. Если ординал конечный, в результате получается фиксированное количество стрелок. Ординал ω дает n – 1 стрелку. Использование же ординала ω + 1 позволяет нам применить рекурсию к количеству стрелок n раз – а это уже фантастический скачок, невероятно увеличивающий мощность рекурсии.
Возьмем для примера функцию 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), у которого есть и более звучное название: ординал Фефермана – Шютте, в честь впервые описавших его американского философа и логика Соломона Фефермана и немецкого математика Карла Шютте. Несмотря на то, что гамма-ноль – все еще счетный ординал и есть после него и другие, определить его можно, только используя несчетные ординалы (то есть такие, которые невозможно получить путем перестановки элементов алеф-нуля; для несчетных ординалов требуется алеф-один или больше элементов). Этот процесс напоминает ход развития самой быстрорастущей иерархии. Как для описания громадных конечных чисел нам пришлось в быстрорастущей иерархии прибегнуть к бесконечным ординалам, так и для описания огромных счетно-бесконечных ординалов мы вынуждены обратиться к ординалам несчетным. В языке просто не существует эпитетов, способных адекватно описать величину конечных чисел, которые можно получить с помощью рекурсии, используя ординал Фефермана – Шютте и другие, следующие за ним. Ни один математик, будь он хоть семи пядей во лбу, не в силах постичь всю безмерность чисел, порождаемых рекурсивными методами. Что, впрочем, нисколько не мешает математикам изобретать все более и более эффективные способы, генерирующие большие числа. Один из самых примечательных методов – функция TREE.
И вот наконец мы добрались до умопомрачительно большого ординала гамма-ноль (Γ0), у которого есть и более звучное название: ординал Фефермана – Шютте, в честь впервые описавших его американского философа и логика Соломона Фефермана и немецкого математика Карла Шютте. Несмотря на то, что гамма-ноль – все еще счетный ординал и есть после него и другие, определить его можно, только используя несчетные ординалы (то есть такие, которые невозможно получить путем перестановки элементов алеф-нуля; для несчетных ординалов требуется алеф-один или больше элементов). Этот процесс напоминает ход развития самой быстрорастущей иерархии. Как для описания громадных конечных чисел нам пришлось в быстрорастущей иерархии прибегнуть к бесконечным ординалам, так и для описания огромных счетно-бесконечных ординалов мы вынуждены обратиться к ординалам несчетным. В языке просто не существует эпитетов, способных адекватно описать величину конечных чисел, которые можно получить с помощью рекурсии, используя ординал Фефермана – Шютте и другие, следующие за ним. Ни один математик, будь он хоть семи пядей во лбу, не в силах постичь всю безмерность чисел, порождаемых рекурсивными методами. Что, впрочем, нисколько не мешает математикам изобретать все более и более эффективные способы, генерирующие большие числа. Один из самых примечательных методов – функция TREE.
Как явствует из названия функции, она напоминает обычное дерево, растущее в лесу, или генеалогическое древо с ветвями, отходящими от общего ствола. Математические деревья – это особая разновидность так называемых графов. Их не нужно путать с графиками. График мы обычно представляем себе как кривую, показывающую соответствие между двумя величинами. Граф же в математике – нечто иное: это способ представления данных, когда точки, называемые узлами или вершинами, соединены отрезками – ребрами. Если, начав с одного из узлов графа и передвигаясь по его ребрам к другим узлам, можно вернуться к исходному, ни разу не проходя ни по одному ребру или узлу дважды, такой маршрут, и сам граф, называется циклом. Если от любого узла можно добраться до любого другого, не проходя дважды ни по одному ребру или узлу, то пройденный маршрут именуют путем, а граф – связным. Деревом называется связный граф, не содержащий циклов. И генеалогические, и биологические деревья имеют именно такую структуру. Если все узлы графа пронумеровать или присвоить им неповторяющиеся цвета, то такое дерево называется помеченным. Если одну из вершин дерева обозначить каккорень, то получается корневое дерево. Одно из полезных свойств корневого дерева состоит в том, что от любого его узла можно проследить путь к корню.
Некоторые из математических деревьев, имеющих ту же структуру ветвей, что и у реального дерева, можно встроить в другие аналогичные деревья. Их называют “гомеоморфно вложимыми”. На простом языке это означает, что они похожи по форме или виду и одно из них – уменьшенный вариант другого. У математиков, конечно, есть для этого термина более точное определение. Они начинают с большего по размеру дерева и смотрят, как сильно можно “обрезать” его крону, используя два метода. Первый – удаление узлов. Если есть узел (кроме корневого), с которым соединены всего два ребра, его можно удалить, а ведущие к нему ребра срастить в одно. Второй метод – удаление ребер. Если два узла соединены единственным ребром, то это ребро стягивается, а узлы на его концах сливаются в один. Цветом получившегося нового узла становится цвет того из них, который был ближе к корню. Если можно, применяя эти две операции в любом порядке, из большего дерева получить меньшее, то говорят, что меньшее дерево гомеоморфно вложимо в большее. Американский математик и статистик Джозеф Краскал доказал важную теорему, связанную с ними. Предположим, у нас есть ряд деревьев, в котором первое дерево может иметь только один узел, второе – не больше двух узлов, третье – не больше трех и так далее; при этом ни одно не может быть гомеоморфно вложено ни в какое из последующих. Краскал обнаружил, что рано или поздно такая последовательность должна закончиться. Но какой может быть ее максимальная длина?
В ответ на поставленный вопрос американский математик и логик Харви Фридман, занесенный в 1967 году в “Книгу рекордов Гиннесса” как самый молодой университетский преподаватель в мире (в Стэнфорде в возрасте 18 лет), определил “функцию дерева” TREE(n) в качестве максимальной длины такой последовательности, где n – количество цветов для вершин. Фридман изучил выходные значения функции для различных значений n. Первое дерево состоит из единственного узла, имеющего определенный цвет, который нельзя использовать снова. Если n = 1, то этот цвет – единственный и последовательность тут же завершается, а значит, TREE(1) = 1. Если n = 2, у нас есть еще один цвет. Второе дерево может иметь до двух узлов включительно, так что содержит два узла, окрашенных в этот второй цвет. Третье дерево также должно содержать только этот цвет, но может иметь только один узел, поскольку иначе второе дерево будет гомеоморфно вложимо в третье. Больше в этом случае деревьев быть не может, поэтому TREE(2) = 3. И вот мы дошли до TREE(3) – и тут, как обнаружил Фридман, происходит нечто невероятное, настоящий взрыв. Совершив гигантский скачок, количество узлов внезапно вырастает до размеров, намного превышающих число Грэма, и достигает в быстрорастущей иерархии малого ординала Веблена – совсем не малого числа, которое мы уже упоминали, путешествуя по различным бесконечностям.
Гугология – поиск новых способов определения все бо́льших и бо́льших чисел – стала настолько популярной, что в этой области уже проводятся конкурсы. Один из первых, Bignum Bakeoff, организовал в 2001 году американский вундеркинд Дэвид Мейз. Перед участниками стояла задача написать на языке C программу не длиннее 512 символов (не считая пробелов), возвращающую как можно большее число. Поскольку для реального выполнения поданных на конкурс программ современным компьютерам понадобилось бы больше времени, чем существует Вселенная, код анализировали вручную, а победителя определяли на основании позиции в быстрорастущей иерархии. Первое место заняла программа loader.c, названная именем ее автора Ральфа Лоудера из Новой Зеландии. Для вычисления окончательного результата потребовались бы невероятно долгое время и машина с чудовищным объемом памяти. Но если бы это все же было возможно, то полученное число Лоудера затмило бы собой и TREE(3), и некоторых других героических обитателей гугологического космоса: таких, например, как SCG(13) – тринадцатый элемент последовательности, именуемой “числа субкубических графов” (схожей с последовательностью TREE, но состоящей из графов, в которых у каждой вершины не больше трех ребер).
В 2007 году в рамках конкурса Big Number Duel в непримиримом поединке за самое большое число сошлись двое философов, старых школьных приятелей – Агустин Райо (он же Мексиканский Множитель) из Массачусетского технологического института и Адам Элга (он же Доктор Зло) из Принстона. Победителем становился тот, кто даст определение самому колоссальному числу. Схватка, в которой обмен остротами и сложнейшая математическая, логическая и философская полемика сочетались с драматизмом боя за звание чемпиона мира по боксу, проходила в забитой до отказа аудитории центра “Стата” МТИ. Первый удар нанес Элга, начертав на доске единицу (видимо, в надежде, что его соперник не в форме). Райо незамедлительно парировал этот выпад, заполнив единицами всю доску. Элга тут же удалил часть линии у основания всех единиц, кроме первых двух, превратив их тем самым в знаки факториала. Так поединок продолжался, постепенно выходя за рамки знакомой математики, пока соперники не стали на ходу изобретать собственную нотацию для все больших чисел. Говорят, что в какой-то момент один из зрителей спросил Элгу: “А это число вообще можно вычислить?” На что тот после краткой паузы ответил: “Нет”. Наконец Райо отправил соперника в нокаут сокрушительным числом, описанным им как “наименьшее положительное число, большее любого конечного положительного числа, которое может быть выражено на языке теории множеств первого порядка с использованием не более чем гугола символов”. Мы не знаем, насколько велико число Райо, и, скорее всего, никогда не узнаем. Ни один компьютер никогда не сумеет его вычислить, даже если бы во Вселенной хватило места для гугола символов. Дело здесь не в нехватке места или времени: число Райо невычислимо, так же как неразрешима проблема остановки.
Афиша конкурса Big Number Duel, проходившего в Массачусетском технологическом институте.
На сегодняшний день, если говорить о более-менее осмысленных больших числах, число Райо – своего рода граница, отделяющая нас от неизвестного. Называли и бо́льшие числа, такие, например, как BIG FOOT, объявленное в 2014 году. Но чтобы получить хотя бы смутное представление о BIG FOOT, нам придется погрузиться в странную область под названием “вселенная куч” (oodleverse) и выучить язык теории куч первого порядка – а здесь не обойтись без ученой степени в области высшей математики и очень своеобразного чувства юмора. Да и в любом случае все самые большие на сегодня числа построены по тому же принципу, что и число Райо.
Чтобы еще глубже проникнуть в бескрайнее пространство чисел, гугологам нужно развивать существующие методики или разрабатывать новые, так же как освоение все более дальних просторов космоса требует новых прорывов, больших и малых, в двигателестроении. А пока охотникам за большими числами придется полагаться на те же приемы, что использовал Райо, только применять их уже к расширенной версии теории множеств первого порядка. Можно, например, добавить в нее аксиомы, которые позволят оперировать бесконечностями еще более грандиозного масштаба, а с их помощью уже генерировать новые рекордные конечные числа.
Если говорить начистоту, вся эта суета с описанием больших чисел ради рекордов не слишком волнует профессиональных математиков, так же как они не видят особого смысла в вычислении все большего и большего количества знаков числа пи. Гугология все же скорее хобби – этакий интеллектуальный мачизм, гонки NASCAR для специалистов по теории чисел. В то же время нельзя сказать, что пользы от нее никакой: она помогает нам осознать пределы нашей сегодняшней математической вселенной, подобно тому как наблюдение небесных тел с помощью самых мощных телескопов раздвигает границы физического космоса.
Заманчиво думать, что огромные числа вроде числа Райо дают нам возможность немножко приблизиться к бесконечности. Но на самом деле это не так. Бесконечные числа можно использовать для получения конечных, но конечное и бесконечность никогда не сольются. Правда в том, что, как бы мы ни старались, какие бы методики ни изобретали для описания все бо́льших и бо́льших чисел, мы ни на шаг не ближе к бесконечности, чем в детстве, когда умели считать только до трех.
10169
2021.03.28 10:55:27