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

Итак, мы достигли ступеньки f 1( n ) на лестнице быстрорастущей иерархии. Следующая ступенька, f 2( n ), подставляет функцию f 1( n ) саму в себя n раз. Ее можно записать как f 2( n ) = f 1( f 1(… f 1( n ))) = n × 2 × 2 × 2 × … × 2, где количество двоек равно n . Это то же самое, что n × 2 n , где 2 n – показательная функция. Если подставить вместо n , скажем, 100, то мы получим f 2(100) = 100 × 2 100 = = 126 765 060 022 822 940 149 670 320 537 600, или приблизительно 127 миллиардов миллиардов триллионов. Будь это сумма на банковском счете, такое состояние даже Биллу Гейтсу могло бы только во сне присниться, а ведь она гораздо меньше, чем некоторые из известных чисел, что нам уже встречались, таких как гугол. Меньше она и суммы самого крупного в истории иска о компенсации ущерба. Иск на 2 ундециллиона (то есть два триллиона триллионов триллионов) долларов был подан 11 апреля 2014 года жителем Манхэттена Энтоном Пьюрисимой, утверждавшим, что в городском автобусе его покусала “больная бешенством” собака. В бессвязном исковом заявлении на 22 страницы, написанном от руки, к которому была приложена фотография несуразно огромной повязки на среднем пальце, Пьюрисима требовал от управления городского транспорта Нью-Йорка, аэропорта Ла-Гуардия, кафе Au Bon Pain (где его якобы регулярно обсчитывали при покупке кофе), университетского медицинского центра города Хобокена и сотен других организаций выплаты компенсации на общую сумму, превышающую всю денежную массу на планете. В мае 2017 года иск был отклонен “за недостаточностью правовых и фактических оснований”. Будем надеяться, что познания Пьюрисимы в математике не распространяются на быстрорастущую иерархию – иначе за этим иском могут последовать другие, на еще бо́льшие суммы (раньше он уже подавал в суд на несколько крупных банков, Международный музыкальный фонд Лан Лана и Китайскую Народную Республику).

Функция f 3( n ) представляет собой n повторений функции f 2( n ), а получающееся в результате число чуть превышает 2 в степени n в степени n в степени n … со степенной башней высотой в n этажей. Это этап двух стрелок, или тетрации, – операции, что мы встречали на подступах к числу Грэма. Дальше продолжаем в том же духе: f 4( n ) – это три стрелки, f 5( n ) – четыре стрелки и так далее; то есть каждое увеличение ординала на единицу равносильно добавлению очередной стрелки и еще одному шагу к количеству стрелок n – 1. Это дает уже реально большие числа – не только по повседневным меркам, но даже по меркам сутяжника Пьюрисимы. Однако, если добавлять всего по одной стрелке за раз, даже до числа Грэма не скоро доберешься, не говоря уже о других, гораздо более солидных экземплярах. Здесь нужно какое-то неожиданное решение. Чтобы получить действительно колоссальные конечные числа, нам придется прибегнуть к помощи чисел бесконечных.

Как мы помним из предыдущей главы, самая маленькая из бесконечностей – это алеф-ноль, бесконечность натуральных чисел. Меняться по величине, то есть по количеству того, что в нем содержится, алеф-ноль не может, зато может меняться по длине – в зависимости от того, как его содержимое организовано. Самая маленькая длина алеф-нуля обозначается бесконечным ординалом омега ( ω ). Следующая – ω + 1, за ней ω + 2, потом ω + 3 и так далее, без конца. Эти бесконечные ординалы – они называются счетными, потому что их можно расставить по порядку, пронумеровать, – служат нам своего рода трамплином для прыжка в мир самых больших из когда-либо описанных конечных чисел. Для начала нам нужно определить, что подразумевается под функцией f ω ( n ), где в качестве индекса стоит наименьший из бесконечных ординалов. Просто отнять 1 и применить рекурсию, о которой мы говорили выше, здесь не получится, поскольку такого понятия, как ω – 1, не существует. Вместо этого мы определяем f ω ( n ) как f n ( n ). Заметьте, это не значит, что ω = n . Мы просто выражаем f ω ( n ) через (конечные) ординалы, меньшие ω , чтобы привести функцию к виду, удобному для вычислений. Вы, возможно, возразите и скажете, что с таким же успехом можно просто написать f n ( n ) вместо f ω ( n ) и получить тот же результат; но тогда нам не удастся сделать следующий шаг – а именно он является решающим и позволяет раскрыть весь невероятный потенциал, заложенный в быстрорастущей иерархии. Как только мы переходим от f ω ( n ) к f ω+ 1( n ), происходит нечто качественно новое. Мы помним, что, увеличивая на единицу ординал, стоящий в индексе функции, мы подставляем предыдущую функцию саму в себя n раз. Если ординал конечный, в результате получается фиксированное количество стрелок. Ординал ω дает n – 1 стрелку. Использование же ординала ω + 1 позволяет нам применить рекурсию к количеству стрелок n раз – а это уже фантастический скачок, невероятно увеличивающий мощность рекурсии.

Возьмем для примера функцию f ω + 1(2). Согласно нашему рекурсивному правилу, она равносильна f ω ( f ω (2)). Раз мы определили f ω (2) как f n (2), то можем записать f ω + 1(2) как f ω ( f 2(2)), просто заменив внутреннюю ω на 2. (Узнать значение внешней f ω нельзя до тех пор, пока нам не будет известно, какое значение примет внутренняя.) Поскольку f 2(2) = 8, от f ω + 1(2) у нас остается f ω (8). Наконец, мы можем упростить внешнюю ω и получить f 8(8), включающую в себя семь стрелок. Этот пример, хоть и показывает, как можно использовать функцию f ω + 1для применения рекурсии к количеству стрелок, не дает полного представления о внушительных возможностях этой функции. Они становятся очевидными только по мере роста n и числа соответствующих ему петель обратной связи. При n = 64 получаем f ω + 1(64), что приблизительно равно числу Грэма. Следующая ступенька быстрорастущей иерархии, f ω + 2( n ), открывает принципиально новые горизонты: на этом этапе весь математический аппарат, послуживший нам для достижения числа Грэма, подставляется сам в себя. В результате получается число, которое можно приближенно записать как g g … 64(с 64 уровнями g в подстрочном индексе), но хотя бы отдаленно представить себе его масштаб не стоит даже пытаться.

Счетно-бесконечные ординалы простираются насколько хватает глаз, и каждый последующий из них – основа для новой, более мощной рекурсивной функции, оставляющей далеко позади предыдущую. Одни омеги составляют ряд такой длины, что он заканчивается только на омеге, возведенной в степенную башню высотой в омегу омег. Этот могучий ординал – эпсилон-ноль – настолько велик, что его невозможно описать средствами нашей классической арифметики, называемой арифметикой Пеано. С каждым шагом вдоль нескончаемой дороги омег конечное число, получаемое путем применения рекурсии, увеличивается на непостижимую величину. Но за самой величественной степенной башней из омег высятся башни, сложенные из многочисленных ярусов еще более внушительных бесконечных ординалов: сначала эпсилонов, потом дзет и так далее, и несть им числа – как мы уже выяснили раньше, когда говорили о бесконечности. С постоянным ростом ординалов растет и эффект обратной связи. И вот наконец мы добрались до умопомрачительно большого ординала гамма-ноль (Γ 0), у которого есть и более звучное название: ординал Фефермана – Шютте, в честь впервые описавших его американского философа и логика Соломона Фефермана и немецкого математика Карла Шютте. Несмотря на то, что гамма-ноль – все еще счетный ординал и есть после него и другие, определить его можно, только используя несчетные ординалы (то есть такие, которые невозможно получить путем перестановки элементов алеф-нуля; для несчетных ординалов требуется алеф-один или больше элементов). Этот процесс напоминает ход развития само2й быстрорастущей иерархии. Как для описания громадных конечных чисел нам пришлось в быстрорастущей иерархии прибегнуть к бесконечным ординалам, так и для описания огромных счетно-бесконечных ординалов мы вынуждены обратиться к ординалам несчетным. В языке просто не существует эпитетов, способных адекватно описать величину конечных чисел, которые можно получить с помощью рекурсии, используя ординал Фефермана – Шютте и другие, следующие за ним. Ни один математик, будь он хоть семи пядей во лбу, не в силах постичь всю безмерность чисел, порождаемых рекурсивными методами. Что, впрочем, нисколько не мешает математикам изобретать все более и более эффективные способы, генерирующие большие числа. Один из самых примечательных методов – функция TREE.