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

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

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

Определение

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

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

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

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

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

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

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

[math]\displaystyle{ X \to p \to (q+1) = X \to (X \to ( \ldots (X \to (X) \to q) \ldots ) \to q) \to q }[/math],

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

Здесь:

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

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

[math]\displaystyle{ a \to b \to c \neq (a \to b) \to c \neq a \to (b \to c) }[/math]

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

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

[math]\displaystyle{ a \to b \to k = a\uparrow^k b. }[/math]

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

[math]\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} }[/math]

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

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

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

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