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

Как мы помним из предыдущей главы, самая маленькая из бесконечностей – это алеф-ноль, бесконечность натуральных чисел. Меняться по величине, то есть по количеству того, что в нем содержится, алеф-ноль не может, зато может меняться по длине – в зависимости от того, как его содержимое организовано. Самая маленькая длина алеф-нуля обозначается бесконечным ординалом омега ( ω ). Следующая – ω + 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.