Когда простых арифметических операций уже не хватает. Как Дональд Кнут придумал стрелки для записи нереально больших чисел

У славянских народов в быту для обозначения невообразимо большого количества использовалось слово «тьма», а древние греки говорили про мириады. Однако и то и другое в современной трактовке не выходило за рамки того, что можно написать на бумаге за вменяемое количество времени: тысячи, десятки тысяч, миллионы, миллиарды….

Однако с развитием математики масштабы человеческой мысли уходили всё дальше и дальше за горизонт. Уже в третьем веке до нашей эры Архимед представил нотацию (способ записи) числа, которое мы бы сейчас записали как:

Уже это число ЗНАЧИТЕЛЬНО превышает диаметр видимой части Вселенной, но, однако «пасует» перед гипотетическим количеством всех возможных реально существующих параллельных вселенных (включая ту, в которой мы находимся):

Обратите внимание, что в подобных записях мы пользуемся правилом правой ассоциативности, т.е. сначала вычисляем 10^7, затем 10^(10^7) и т.д.

Однако, математикам двадцатого века встретились такие задачи, численное решение которых многократно, невообразимо затмевает даже это исполинское число.

Совокупность таких задач объединяется в теорию Рамсея — раздел комбинаторики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура». Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.

Одна из таких задач породила число Грэма, которое с помощью известных математических операций записать уже не удавалось: даже последовательное возведение в степень и в степень и в степень…., как в числах, что мы видели раньше, не поспевало за ростом этой величины.

Берем куб, соединяем все его вершины между собой, а затем анализируем все возможные его раскраски в два цвета. Например, для обычного трехмерного куба есть такая раскраска (и не одна), что в ней найдется полносвязный 4-подграф, все вершины которого лежат в одной плоскости.

Однако сама проблема Грэма многократно сложнее: нужно найти минимальную размерность гиперкуба, при котором каждая раскраска будет содержать такой такой одноцветный 4-подграф.

Например, нужно взять четырехмерный куб, просчитать все его раскраски в два цвета, а затем их проанализировать на предмет компланарных (содержащихся в одной плоскости) 4-подграфов одного цвета. Если хотя бы одна раскраска не будет удовлетворять условию, то размерность повышается…

Изменив цвет всего лишь одного ребра, мы найдем раскраску, в которой компланарного 4-подграфа уже нет. Значит, идем дальше в сторону увеличения размерности

Удивительно, но оказалось, что эта задача из 1971 года точно имеет решение. Оценили его достаточно широко: размерность нужного гиперкуба в пределах, как говорится, отсюда и до обеда…

И вот эту верхнюю границу размерности G, которое называется числом Грэма, уже нельзя записать привычным образом. Оно настолько велико, что наблюдаемая Вселенная слишком мала, чтобы содержать его обычное цифровое представление, предполагая, что каждая цифра занимает один планковский объем.

Даже запись этого числа в виде неимоверно огромной башни степеней не имеет смысла: она не поместится во Вселенной.

Тем не менее математики нашли способ его обозначения. В 1947 г английский математик Рубен Гудстейн ввел в научный оборот термин тетрация.

Однако и этого окажется недостаточно, потому что для обозначения малого числа Грэма приходится использовать операции еще большего порядка, чем тетрация.

В 1976 году американский математик Дональд Кнут придумал специальную стрелочную нотацию, получившую его имя. Одна стрелка — это просто возведение в степень, две стрелки — это упомянутая выше тетрация:

С трех стрелок уже начинается интересное:

Уже начинает захватывать дух! Тем более, что мы можем как увеличивать основания степеней, так и количество стрелок, что сразу приводит к дикому росту.

Теперь мы подошли к тому, чтобы попытаться записать число Грэма , однако и здесь нас ждет неожиданность! Оказывается, даже количество стрелок будет записываться через стрелочную нотацию, да еще и 64-ю уровнями вложенности!

Оценим эту запись. Цифра 64 обозначает количество слоев вложенности, 4 — количество стрелок в самом нижнем слое, а вторая строчка говорит о том, что обрамлять стрелки будет цифра 3, и количество стрелок на каждом следующем уровне будет равно числу, рассчитанному на уровне ниже.

Чтобы понять, что мы не в состоянии понять масштаб числа Грэма, можно рассмотреть такое число:

А теперь представьте, что в числе Грэма аж целых 64 слоя, да и начинается оно с 4 стрелок!

Интересно, что согласно известному принципу Арнольда, в названиях математических теорем часто не указывается их настоящий создатель. Так вышло и здесь: число Грэма было найдено известным математиком и популяризатором Мартином Гарднером в 1977 году (через год после изобретения стрелочной нотации Кнута).

Впрочем, число Грэма недолго было самым большим согласно Книге рекордов Гиннеса. В современной математике есть и более чудовищные экземпляры, например, число усердного бобра