Русская Википедия:Стрелочные обозначения Конвея

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Определение

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

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

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

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

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

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

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

<math>X \to p \to (q+1) = X \to (X \to ( \ldots (X \to (X) \to q) \ldots ) \to q) \to q</math>,

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

Здесь:

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

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

<math>a \to b \to c \neq (a \to b) \to c \neq a \to (b \to c)</math>

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

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

<math>a \to b \to k = a\uparrow^k b.</math>

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

<math>

 \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>

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

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

<math>

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