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

Математическую проблему, из которой родилось число Грэма, фантастически сложно решить, но довольно легко сформулировать. Связана она с многомерными кубами, то есть n -мерными гиперкубами. Представьте, что все вершины такого куба попарно соединены друг с другом отрезками, окрашенными либо в красный, либо в синий цвет. Грэм задался следующим вопросом: каково наименьшее значение n , при котором для любого варианта окрашивания найдутся четыре вершины, лежащие в одной плоскости и попарно соединенные отрезками одного цвета? Ему удалось доказать, что нижний предел для числа n – 6, а верхний – g 64. Этот колоссальный разрыв свидетельствует о сложности задачи. Грэм смог доказать, что значение n , удовлетворяющее ее условиям, существует, но для этого ему пришлось определить верхний предел n с помощью числа умопомрачительной величины. С тех пор математики сумели сократить разрыв до более скромного (по сравнению с первоначальным) диапазона значений n : от 13 до 9↑↑↑4.

Число Грэма, наряду с гуголом и гуголплексом, часто приводят в качестве примера очень большого числа, имея о нем, однако, весьма смутное понятие. Во-первых, это уже далеко не самое большое из описанных чисел. Во-вторых, если уж искать новые “рекордные” числа и способы их представления и описания, то брать за основу число Грэма и увеличивать его с помощью традиционных математических операций не имеет никакого смысла.

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

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

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

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

Искусство, музыка, язык, вычислительные системы, математика – рекурсия встречается во всех этих областях; она многолика, но это всегда нечто, что возвращается к самому себе. Иногда в результате получается просто бесконечно повторяющаяся петля. Возьмите, к примеру, шуточную словарную статью: “Рекурсия. См. рекурсия ”. Более детально проработана рекурсивная петля в литографии Маурица Эшера “Картинная галерея” (1956 года), на которой изображено здание городской галереи, в которой выставлена картина, изображающая здание галереи, в которой… и так далее. Классический пример рекурсии в технике – обратная связь, когда выходной сигнал системы подается на ее вход. С этой проблемой нередко приходится сталкиваться, например, рок-музыкантам, если микрофон на сцене расположен перед акустической системой, к которой он подключен. Звук, принимаемый микрофоном, усиливается и подается на динамик системы, откуда вновь поступает на микрофон, и так продолжается до тех пор, пока – довольно скоро – из-за усиления при каждом прохождении цикла звук не превратится в знакомый пронзительный свист. Рекурсия в математике работает примерно так же, только вместо электронной системы “микрофон – усилитель – динамик” здесь функция, которая обращается к самой себе, так что ее выходное значение подается опять на вход.