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

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

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

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

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

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

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

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

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

Здесь:

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

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

${\displaystyle a\to b\to c\neq (a\to b)\to c\neq a\to (b\to c)}$

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

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

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

${\displaystyle {\begin{matrix}a\to b=a\to b\to 1=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b\,\mathrm {pa} \scriptstyle {3}\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\to b\to 2={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} \\&b\,\mathrm {pa} \scriptstyle {3}\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\to b\to 3=&\underbrace {{}^{^{^{^{^{a}}}}}{}^{^{^{^{^{.}}}}}{}^{^{^{^{.}}}}{}^{^{^{.}}}{}^{a}a} \\&b\,\mathrm {pa} \scriptstyle {3}\end{matrix}}}$