Число Грэма

Краткое определение числа Грэма.

Число Грэма (англ. Graham's number) — Огромное число, которое являлось верхней границей решения определенной задачи теории Рамсея. Это некая очень большая степень тройки, записанная с использованием нотации Кнута. Он назван в честь Рональда Грэма.

Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где он написал: «В неопубликованном доказательстве Грэм недавно установил настолько большую границу, что она является рекордсменом». для самого большого числа, когда-либо использовавшегося в серьёзном математическом доказательстве».

В 1980 году Книга рекордов Гиннеса подтвердила утверждения Гарднера, что еще больше увеличило интерес к этому числу. Число Грэма — невообразимое число, которое больше других известных больших чисел, таких как числа Гугола, Гуголплекса, Скьюза и числа Мозера. Вся наблюдаемая Вселенная слишком мала, чтобы вместить обычную десятичную запись чисел Грэма (предполагается, что каждая цифра занимает как минимум планковский объем). Даже образуют силовые башни $a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}$бесполезны для этой цели (в том же смысле), хотя числа можно записать с использованием рекурсивных формул, таких как нотация Кнута или ее эквивалент, как это сделал Грэм. Последние 500 цифр числа Грэма:

...02425950695064738395657479136519351798334535362521430035401260267716226721604198106522631693551887803881448314065252616878509555264605107117200099709291249544378887496062882911725063001303622934916080254594614945788714278323508292421020918258967535604308699380168924988926809951016905591995119502788717830837018340236474548882222161573228010132974509273445945043433009010969280253527518332898844615089404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387.

В современных математических доказательствах мы иногда встречаем числа, даже превышающие число Грэма, например, когда имеем дело с конечной формой Фридмана в теореме Краскала – называемым TREE(3).

В стрелочных обозначениях число Грэма указано для 64-го члена в следующем порядке:

$G(0) = 4$
$G(1) = 3 \uparrow\uparrow\uparrow\uparrow 3$
Для 0 ⩽ k < 64,$G(k+1) = 3\underbrace{\uparrow\ ... \uparrow}_{G(k)} 3$

Число Грэма = $G(64) =$

$\left. 3\underbrace{\uparrow\ ... \uparrow}_{3\underbrace{\uparrow\ ... \uparrow}_{\underbrace{...}_{3\underbrace{\uparrow\ ... \uparrow}_{3 \uparrow\uparrow\uparrow\uparrow 3} 3} } 3} 3 \right \} 64$

Число Грэма обычно считается самым большим числом, когда-либо использовавшимся в серьезных математических доказательствах, хотя на это звание претендовали гораздо большие числа (например, TREE(3) и SCG(13). Наименьший Бауэрсизм, превышающий число Грэма, - это капрал, а наименьший сибианизм, превышающий число Грэма, - Гратаголд.

Проблема Грэма

Число Грэма связано со следующей проблемой теории Рамсея:

Рассмотрим $n$-мерный гиперкуб и соединим все пары вершин для получения полного графа с $2^n$ вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении $n$ каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, $N^*$, и показали, что $6\leqslant N^{*}\leqslant N$, где $N$ — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как $N=F^{7}(12)$, где $F(n) = 2 \uparrow^{n} 3$. Это число именуется как «малое число Грэма» (англ. Little Graham).

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что $N^*$должно быть не меньше 13. Потом последовало и улучшение верхней границы до $2\uparrow ^{3}6$ и затем до $2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$. Таким образом, $13\leqslant N^{*}\leqslant 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$.

Предметом настоящей статьи является верхняя граница $G$ , которая много слабее (то есть больше), чем $N$: $G=f^{64}(4)$, где $f(n)=3\uparrow ^{n}3$. Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

Определение числа Грэма

При использовании Стрелочной нотации Кнута число Грэма G может быть записано как

$\left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 слоя}}$

где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть

$G=g_{64},$где $g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,$

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, $G$ вычисляется в 64 шага: на первом шаге мы вычисляем $g_1$ с четырьмя стрелками между тройками, на втором — $g_1$ с $g_{2}$ стрелками между тройками, на третьем — $g_3$ с $g_{2}$ стрелками между тройками и так далее; в конце мы вычисляем $G=g_{64}$с $g_{63}$ стрелок между тройками.

Это может быть записано как

$G=f^{64}(4)$, где $f(n)=3\uparrow ^{n}3,$

где верхний индекс у $f$ означает итерации функций. Функция $f$ является частным случаем гипероператоров $f(n)={\text{hyper}}(3,n+2,3)$ и может также быть записана при помощи цепных стрелок Конвея как $f(n)=3\rightarrow 3\rightarrow (n+2)$. Последняя запись также позволяет записать следующие граничные значения для $G$:

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.$

С помощью массивной нотации Бауэрса границы числа Грэма можно записать как:

{3,64,1,2} < G < {3,65,1,2}.

Масштаб числа Грэма

Для того чтобы осознать невероятно огромный размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g₁) стремительно растущей 64-членной последовательности (т. н. «грааль», Grahal). На языке тетраций $\uparrow\uparrow$ означает:

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow {\Bigl (}3\uparrow \uparrow {\bigl (}3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots {\bigr )}{\Bigr )}$,

где число троек в выражении справа

$3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3).$

Теперь каждая тетрация ($\uparrow\uparrow$) по определению разворачивается в «степенную башню» как

$3\uparrow \uparrow X\ =\ 3\uparrow {\Bigl (}3\uparrow {\bigl (}3\uparrow \dots (3\uparrow 3)\dots {\bigr )}{\Bigr )}\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}$, где X — количество троек.

Таким образом,

$g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))$, где количество троек — $3\uparrow \uparrow (3\uparrow \uparrow 3)$.

Оно может быть записано на языке степеней:

$g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3\quad$, где число башен — $\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3$,

где количество троек в каждой башне, начиная слева, указывается предыдущей башней.

Другими словами, $g_1$ вычисляется путём вычисления количества башен, $n=3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}$ (где число троек — $3^{3^3}$ = Шаблон:Num), и затем вычисления $n$ башен в следующем порядке:

1-я башня: 3

2-я башня: 3↑3↑3 (количество троек — 3) = Шаблон:Num

3-я башня: 3↑3↑3↑3↑…↑3 (количество троек — Шаблон:Num) = …

.

.

.

$g_1$ = $n$-я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления $(n-1)$-й башни)

Масштаб первого члена, $g_1$, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя $n$ — это всего лишь количество башен в этой формуле для $g_1$, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно $4\cdot 10^{185}$). Оно уже больше гуголплекса, и вся запись с 7625597484987 тройками уже на третьей башне (так называемое «тритри», Tritri) будет занимать расстояние от Земли до Солнца. Даже башня с четырьмя тройками $3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\approx 1{,}3\times 10^{3\,638\,334\,640\,024}$ представляет собой уже слишком большое число, чтобы представить его непосредственно. После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.

Сравнение

Поскольку G(0) равно 4, а не 3, число Грэма не может быть эффективно выражено в цепной нотации стрел $G(64) \approx 3 \rightarrow 3 \rightarrow 64 \rightarrow 2$ или в BEAF $\{3,65,1,2\} < G(64) < \{3, 66, 1, 2\}$. Используя G-функции Джонатана Бауэрса с базой в 3 это в точности G⁶⁴4. Это также может быть точно выражено в Нотации массива Грэма как $[3,3,4,64]$.

Тим Чоу доказало, что число Грэма намного больше, чем мозер. Доказательство основано на том факте, что, используя нотацию Штайнхауса-Мозера, n в (k + 2)-угольнике меньше, чем $n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n$. Он отправил доказательство Сьюзан Степни 7 июля 1998 года. Так совпало, что Степни получил аналогичное доказательство от Тодда Сезере несколькими днями позже.

Японский гуголог Кёдайсуу доказал, что число Грэма меньше $f_{\omega+1}(64)$ в быстрорастущей иерархии по отношению к иерархии Вайнера.

Сравнение с функцией занятого бобра

• 2010-09-19: Было доказано, что число Грэма намного меньше, чем $\Sigma(64)$.
• 2016-07-24: Согласно пользователю англоязычной гугология вики Wythagoras, он нашёл машину Тьюринга, которая доказывает, что $\Sigma (18) > G(64)$, улучшив машину Deedlit11, и написал краткий набросок доказательства вместо строгого доказательства.
• В этом сообществе считалось, что лучшая верхняя граница $\Sigma(17)$ была кем-то доказана до 2021-07-09, но, по крайней мере, не было ни одного цитируемого источника о результате. Поэтому читатель должен быть осторожен, чтобы он или она не уловили неверную информацию.
• 2021-03-18: Дэнил Нагай утверждает, что его машина Тьюринга с 16 состояниями реализует множественное расширение и превосходит число Грэма, что подразумевает $\Sigma(16) > G(64)$.
  • 2022-07-11: С. Лигоцкий подтвердил, что машина Тьюринга с 16 состояниями Дэниела Нагая превзошла число Грэма

Значения

Нотация	Значение (приблизительное)
Сверхсильная функция	$1^{0}[1]$ (отдаленное значение)
Быстрорастущая Иерархия	$f_{\omega+1}(64)$
Цепная нотация стрел	$3 \rightarrow 3 \rightarrow 64 \rightarrow 2$
Цепная нотация стрел (расширение Выходника)	$3 \rightarrow 3 \rightarrow_{64} 4$ (точное значение)
Иерархия Харди	$H_{\omega^{\omega}64}(64)$
BEAF	$\{3,65,1,2\}$
Расширенная гипер E нотация	E[3]3##4#64
Сильная нотация массива	$s(3,64,2,2)$
Медленнорастущая Иерархия	$g_{\Gamma_{0}}(65)$

Литература

• Шаблон:Статья The explicit formula for N appears on p. 290.
• Graham, R. L.; Rothschild, B.L. (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
• Шаблон:Статья; reprinted (revised 2001) in the following book:
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья