Стрелочные обозначения Конвея

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

По Конвею, большие целые числа представляются последовательностями из $n$ натуральных чисел, соединёнными горизонтальными стрелками (например, 2→3→4→5→6) — цепочками Конвея.

Определение

Цепочка Конвея определяется следующим образом:

• Любое натуральное число представляет собой цепочку единичной длины.
• Цепочка длины $n$, за которой следует стрелка «→» и натуральное число, вместе составляют цепочку длины $n+1$.

Любая цепочка Конвея представляет некоторое целое число. Две цепочки называются равными, если они представляют равные числа.

Общая схема вычисления

Расчёт значения цепочки производится согласно следующим правилам:

1. $p=p$ (цепочка $p$ представляет число $p$);
2. $p\to q=p^{q}$ (цепочка $p\to q$ представляет возведение в степень);
3. $X\to p\to 1=X\to p$;
4. $X\to 1\to q=X$;
5. $X\to p\to (q+1)=X\to (X\to (p-1)\to (q+1))\to q$ при $p>1$.

Два последних правила можно записать в виде одного длинного правила:

$X\to p\to (q+1)=X\to (X\to (\ldots (X\to (X)\to q)\ldots )\to q)\to q$,

где цепочка в правой части содержит $p$ копий подцепочки $X$, $p-1$ копий числа $q$ и $p-1$ пар скобок.

Здесь:

• $p,q$ — некоторые натуральные числа;
• $X$ — в общем случае, некоторая другая цепочка Конвея (подцепочка).

Следует отметить, что цепочки в скобках не входят в общую цепочку и вычисляются отдельно. То есть, в общем случае:

$a\to b\to c\neq (a\to b)\to c\neq a\to (b\to c)$

Частные случаи

Обозначения Конвея связаны с обозначениями Кнута следующим образом:

$a\to b\to k=a\uparrow ^{k}b.$

Возведение в степень в обозначениях Конвея:

$H_{3}(a,b)=a\to b=a\to b\to 1=a^{b}$

Тетрация в обозначениях Конвея:

$H_{4}(a,b)=a\to b\to 2=\underbrace {a^{a^{a^{\cdots ^{a^{a}}}}}} _{\text{b стрелок}}$

Пентация в обозначениях Конвея:

$\left.{\begin{matrix}H_{5}(a,b)=a\to b\to 3=&&\underbrace {a^{a^{a^{\cdots ^{a^{a}}}}}} \\&&\underbrace {a^{a^{a^{\cdots ^{a^{a}}}}}} \\&&\underbrace {\quad \quad \vdots \quad \quad } \\&&\underbrace {a^{a^{a^{\cdots ^{a^{a}}}}}} \\&&{\text{a стрелок}}\end{matrix}}\right\}{\text{b }}$