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

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

По Конвею, большие целые числа представляются последовательностями из $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 (\dots (X\to (X)\to q)\dots )\to q)\to q$,

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

Здесь:

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

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

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

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

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

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

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

$\begin{array}{cc}a\to b=a\to b\to 1=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\mathrm{p}\mathrm{a}3\end{array}$

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

$\begin{array}{cc}a\to b\to 2={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}\\ & b\mathrm{p}\mathrm{a}3\end{array}$

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

$\begin{array}{cc}a\to b\to 3=& \underbrace{{}^{{}^{{}^{{}^{{}^a}}}}{}^{{}^{{}^{{}^{{}^{.}}}}}{}^{{}^{{}^{{}^{.}}}}{}^{{}^{{}^{.}}}{}^{a}a}\\ & b\mathrm{p}\mathrm{a}3\end{array}$