Стрелочные обозначения Конвея
Обозначе́ния Ко́нвея со стре́лками — метод обозначения очень больших целых чисел, предложенный Джоном Конвеем.
По Конвею, большие целые числа представляются последовательностями из [math]\displaystyle{ n }[/math] натуральных чисел, соединёнными горизонтальными стрелками (например, 2→3→4→5→6) — цепочками Конвея.
Определение
Цепочка Конвея определяется следующим образом:
- Любое натуральное число представляет собой цепочку единичной длины.
- Цепочка длины [math]\displaystyle{ n }[/math], за которой следует стрелка «→» и натуральное число, вместе составляют цепочку длины [math]\displaystyle{ n+1 }[/math].
Любая цепочка Конвея представляет некоторое целое число. Две цепочки называются равными, если они представляют равные числа.
Общая схема вычисления
Расчёт значения цепочки производится согласно следующим правилам:
- [math]\displaystyle{ p=p }[/math] (цепочка [math]\displaystyle{ p }[/math] представляет число [math]\displaystyle{ p }[/math]);
- [math]\displaystyle{ p \to q=p^q }[/math] (цепочка [math]\displaystyle{ p \to q }[/math] представляет возведение в степень);
- [math]\displaystyle{ X \to p \to 1 = X \to p }[/math];
- [math]\displaystyle{ X \to 1 \to q = X }[/math];
- [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]
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |