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

В последние годы возник целый раздел занимательной математики под названием “гугология”, посвященный исключительно расширению горизонтов больших чисел путем описания и наименования еще бо́льших экземпляров. В принципе, назвать число, большее любого другого, может кто угодно. Если я назову число Грэма, вы можете сказать “число Грэма плюс 1”, или “число Грэма в степени, равной числу Грэма”, или даже “g₆₄↑↑↑↑…↑g₆₄ c числом стрелок, равным g₆₄” (что примерно равно g₆₅). Но такое “надстраивание” за счет повторного использования одних и тех же математических действий не влечет за собой никаких коренных изменений: в результате все равно получится некая производная числа Грэма. Иначе говоря, придуманное вами число будет построено примерно таким же способом, как и само число Грэма, с помощью аналогичных приемов. Серьезные гугологи называют такую неэлегантную мешанину из уже существующих чисел и функций, никак не затрагивающую исходное большое число по сути, “салатом” и относятся к ней крайне неодобрительно. Число Грэма – это стрелочная нотация, доведенная до предела своих возможностей. В “салате” же к числу Грэма просто применяют какое-нибудь несущественное математическое действие. Такие безыскусные игры со скромным приращением готовых чисел не для гугологов; их интересует разработка принципиально новой системы, которую можно было бы расширить до таких масштабов, чтобы число Грэма показалось пренебрежимо малым. Одна такая бесконечно масштабируемая система уже существует. Она называется быстрорастущей иерархией, поскольку позволяет достичь феноменальных темпов роста. Что еще важнее, эта методика уже опробована математиками на практике и часто используется как эталон при разработке новых способов получения фантастически больших чисел.

Прежде чем говорить о быстрорастущей иерархии, нужно усвоить две вещи. Первое: она представляет собой ряд функций. Функция в математике – это просто соответствие, некое правило, превращающее одно значение, входное, в другое, выходное. Функцию можно представить себе как машинку, которая преобразует одни значения в другие, применяя к ним всегда единый набор действий, например, прибавляя тройку. Если обозначить входное значение буквой x, а функцию записать как f(x) (это произносится как “f от x”), то f(x) = x + 3.

Второе, что нужно знать о быстрорастущей иерархии: в качестве индекса функции (показывающего, сколько раз следует выполнить нужный набор действий) используются порядковые числа – ординалы. Мы уже сталкивались с ними в предыдущей главе, когда говорили о бесконечности. Ординалы указывают на положение того или иного объекта в списке или на порядок расположения элементов в ряду. Они могут быть конечными и бесконечными. С конечными порядковыми числами знакомы все: “пятый”, “восьмой”, “сто двадцать третий” и так далее. А вот бесконечные не на слуху, про них знают лишь те, кто интересуется математикой поглубже. Оказывается, и конечные, и бесконечные ординалы – чрезвычайно полезная штука, когда стоит задача добраться до сверхбольших (но все же конечных) чисел и описать их. Индексирование функций с помощью конечных ординалов позволяет дотянуться до вполне солидных больших чисел. Но когда к делу подключаются бесконечные ординалы, когда именно они начинают определять, сколько раз необходимо выполнить функцию, – вот тут быстрорастущая иерархия проявляет себя в полную силу.

С первой ступенькой иерархии все очень просто: это функция, которая всего-навсего прибавляет к числу единицу. Назовем такую начальную функцию f₀. Предположим, мы хотим пропустить через жернова нашей функции число n. Тогда f₀(n) = n + 1. Но такими крохотными шажками, прибавляя каждый раз по единице, мы не скоро доберемся до больших чисел, поэтому перейдем к функции f₁(n). Она берет предыдущую функцию и подставляет ее саму в себя n раз: другими словами, f₁(n) = f₀(f₀(… f₀(n))) = = n + 1 + 1 + 1 + … + 1, где в общей сложности n единиц, что дает в итоге 2n. И опять-таки не слишком впечатляет – такими темпами нам долго добираться до страны больших чисел. Но зато эта функция наглядно демонстрирует процесс, из которого быстрорастущая иерархия черпает свою невероятную мощь. И процесс тот – рекурсия.