Эта странная математика

Как мы помним из предыдущей главы, самая маленькая из бесконечностей – это алеф-ноль, бесконечность натуральных чисел. Меняться по величине, то есть по количеству того, что в нем содержится, алеф-ноль не может, зато может меняться по длине – в зависимости от того, как его содержимое организовано. Самая маленькая длина алеф-нуля обозначается бесконечным ординалом омега (ω). Следующая – ω + 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. (Узнать значение внешней f_ω нельзя до тех пор, пока нам не будет известно, какое значение примет внутренняя.) Поскольку f₂(2) = 8, от f_ω + 1(2) у нас остается f_ω(8). Наконец, мы можем упростить внешнюю ω и получить f₈(8), включающую в себя семь стрелок. Этот пример, хоть и показывает, как можно использовать функцию f_ω + 1 для применения рекурсии к количеству стрелок, не дает полного представления о внушительных возможностях этой функции. Они становятся очевидными только по мере роста n и числа соответствующих ему петель обратной связи. При n = 64 получаем f_ω + 1(64), что приблизительно равно числу Грэма. Следующая ступенька быстрорастущей иерархии, f_ω + 2(n), открывает принципиально новые горизонты: на этом этапе весь математический аппарат, послуживший нам для достижения числа Грэма, подставляется сам в себя. В результате получается число, которое можно приближенно записать как g_g … 64 (с 64 уровнями g в подстрочном индексе), но хотя бы отдаленно представить себе его масштаб не стоит даже пытаться.