Обозначение цепной стрелки Конвея

Обозначение цепочки стрелок Конвея , созданное математиком Джоном Хортоном Конвеем , является средством выражения некоторых чрезвычайно больших чисел . Это просто конечная последовательность натуральных чисел , разделенных стрелками вправо, например $2\to 3\to 4\to 5\to 6$.

Как и в большинстве комбинаторных обозначений, определение является рекурсивным . В этом случае обозначение в конечном итоге превращается в самое левое число, возведенное в некоторую (обычно огромную) целочисленную степень.

Определение и обзор

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

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

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

Позволять $a,b$ обозначаем положительные целые числа и пусть $\#$ обозначаем неизмененный остаток цепи. Затем:

1. Пустая цепочка (или цепочка длины 0) равна $1$
2. Цепь $p$ представляет число $p$.
3. Цепь $a\rightarrow b$ представляет число $a^{b}$.
4. Цепь $a\rightarrow b\rightarrow c$ представляет число $a\uparrow ^{c}b$ (см. обозначение Кнута, направленное вверх )
5. Цепь $\#\rightarrow 1$ представляет то же число, что и цепочка $\#$
6. В противном случае цепь $\#\rightarrow (a+1)\rightarrow (b+1)$ представляет то же число, что и цепочка $\#\rightarrow (\#\rightarrow a\rightarrow (b+1))\rightarrow b$.

Свойства

1. Цепочка оценивается в совершенную степень своего первого числа.
2. Поэтому, $1\to Y$ равно $1$
3. $X\to 1\to Y$ эквивалентно $X$
4. $2\to 2\to Y$ равно $4$
5. $X\to 2\to 2$ эквивалентно $X\to X$

Интерпретация

Нужно осторожно относиться к цепочке стрел в целом . Цепочки стрелок не описывают повторяющееся применение бинарного оператора. Тогда как цепочки других инфиксных символов (например, 3+4+5+6+7) часто можно рассматривать фрагментами (например (3+4)+5+(6+7)) без изменения смысла (см. ассоциативность ), или, по крайней мере, может быть оценено шаг за шагом в заданном порядке, например 3 ^{4 5 6 7} справа налево, в отличие от цепей для стрел Конвея.

Например:

• $2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=2^{4}=16$
• $2\rightarrow (3\rightarrow 2)=2^{3^{2}}=2^{9}=512$
• $(2\rightarrow 3)\rightarrow 2=(2^{3})^{2}=8^{2}=64$

Шестое правило определения является основным: цепочка из 4 или более элементов, заканчивающаяся 2 или выше, становится цепочкой той же длины с (обычно значительно) увеличенным предпоследним элементом. Но его конечный элемент уменьшается, что в конечном итоге позволяет пятому правилу сократить цепочку. После, перефразируя Кнута , «много деталей», цепочка сокращается до трех элементов, а четвертое правило завершает рекурсию.

Примеры

Примеры быстро усложняются. Вот несколько небольших примеров:

$n$

$=n$ (По правилу 2)

$p\to q$

$=p^{q}$ (По правилу 3)

Таким образом, $3\to 4=3^{4}=81$

$4\to 3\to 2$

$=4\uparrow \uparrow 3$ (По правилу 4)

$=4\uparrow (4\uparrow 4)$

$=4\uparrow 256$

$=4^{256}$

$=13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,$ $546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096$

$\approx 1.34*10^{154}$

$2\to 2\to a$

$=2[\uparrow ^{a}]2$ (По правилу 4)

$=4$ (см. обозначение стрелки вверх Кнута )

$2\to 4\to 3$

$=2\uparrow \uparrow \uparrow 4$ (По правилу 4)

$=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2$

$=2\uparrow \uparrow 2\uparrow \uparrow 4$

$=2\uparrow \uparrow 2\uparrow 2\uparrow 2\uparrow 2$

$=2\uparrow \uparrow 2\uparrow 2\uparrow 4$

$=2\uparrow \uparrow 2\uparrow 16$

$=2\uparrow \uparrow 65536$

$={^{65536}2}$ (см. тетрацию )

$2\to 3\to 2\to 2$

$=2\to 3\to (2\to 3)\to 1$ (По правилу 6)

$=2\to 3\to 8\to 1$ (По правилу 3)

$=2\to 3\to 8$ (По правилу 5)

$=2\to (2\to 2\to 8)\to 7$ (По правилу 6)

$=2\to 4\to 7$ (По правилу 6)

$=2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 4$ (По правилу 4)

= намного больше предыдущего числа

$3\to 2\to 2\to 2$

$=3\to 2\to (3\to 2)\to 1$ (По правилу 6)

$=3\to 2\to 9\to 1$ (По правилу 3)

$=3\to 2\to 9$ (По правилу 5)

$=3\to 3\to 8$ (По правилу 6)

$=3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3$ (По правилу 4)

= намного, намного больше предыдущего числа

примеры

Простейшие случаи с четырьмя членами (не содержащими целых чисел меньше 2):

• $a\to b\to 2\to 2$
  $=a\to b\to 2\to (1+1)$
  $=a\to b\to (a\to b)\to 1$
  $=a\to b\to a^{b}$
  $=a[a^{b}+2]b$

(эквивалент последнего упомянутого свойства)

• $a\to b\to 3\to 2$
  $=a\to b\to 3\to (1+1)$
  $=a\to b\to (a\to b\to (a\to b)\to 1)\to 1$
  $=a\to b\to (a\to b\to a^{b})$
  $=a[a\to b\to 2\to 2+2]b$
• $a\to b\to 4\to 2$
  $=a\to b\to (a\to b\to (a\to b\to a^{b}))$
  $=a[a\to b\to 3\to 2+2]b$

Здесь мы видим закономерность. Если для любой цепи $X$, мы позволяем $f(p)=X\to p$ затем $X\to p\to 2=f^{p}(1)$ (см. функциональные полномочия ).

Применяя это с $X=a\to b$, затем $f(p)=a[p+2]b$ и $a\to b\to p\to 2=a[a\to b\to (p-1)\to 2+2]b=f^{p}(1)$

Так, например, $10\to 6\to 3\to 2=10[10[1000002]6+2]6$.

Двигаемся дальше:

• $a\to b\to 2\to 3$
  $=a\to b\to 2\to (2+1)$
  $=a\to b\to (a\to b)\to 2$
  $=a\to b\to a^{b}\to 2$
  $=f^{a^{b}}(1)$

Опять же, мы можем обобщить. Когда мы пишем $g_{q}(p)=X\to p\to q$ у нас есть $X\to p\to q+1=g_{q}^{p}(1)$, то есть, $g_{q+1}(p)=g_{q}^{p}(1)$. В случае выше, $g_{2}(p)=a\to b\to p\to 2=f^{p}(1)$ и $g_{3}(p)=g_{2}^{p}(1)$, так $a\to b\to 2\to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^{a^{b}}(1)$

Функция Аккермана

Функцию Аккермана можно выразить с помощью обозначения цепочки стрелок Конвея:

$A(m,n)=(2\to (n+3)\to (m-2))-3$ для $m\geq 3$ (С $A(m,n)=2[m](n+3)-3$ в гипероперации )

следовательно

$2\to n\to m=A(m+2,n-3)+3$ для $n>2$

( $n=1$ и $n=2$ будет соответствовать $A(m,-2)=-1$ и $A(m,-1)=1$, что логически можно было бы добавить).

Номер Грэма

Число Грэма не может быть выражено в виде цепочки стрелок Конвея, но оно ограничено следующим:

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$

Доказательство: сначала определим промежуточную функцию $f(n)=3\rightarrow 3\rightarrow n={\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n arrows}}\end{matrix}}$, который можно использовать для определения числа Грэма как $G=f^{64}(4)$. (Верхний индекс 64 обозначает функциональную мощность .)

Применяя правило 2 и правило 4 наоборот, мы упрощаем:

$f^{64}(1)$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))$ (с 64 $3\rightarrow 3$х)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1$

$=3\rightarrow 3\rightarrow 64\rightarrow 2;$

$$\left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}{\text{64 layers}}$$

$f^{64}(4)=G;$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))$ (с 64 $3\rightarrow 3$х)

$$\left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}$$

$f^{64}(27)$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))$ (с 64 $3\rightarrow 3$х)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))$ (с 65 $3\rightarrow 3$х)

$=3\rightarrow 3\rightarrow 65\rightarrow 2$ (расчёты, как указано выше).

$=f^{65}(1)$

$$\left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}{\text{65 layers}}$$

Поскольку f возрастает строго ,

$f^{64}(1)<f^{64}(4)<f^{64}(27)$

что является заданным неравенством.

С помощью цепочек стрелок очень легко указать число, намного большее, чем число Грэма, например: $3\rightarrow 3\rightarrow 3\rightarrow 3$.

$3\rightarrow 3\rightarrow 3\rightarrow 3$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,$

$=f^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)$

$=f^{f^{27}(1)}(1)$

$$\left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matrix}}\right\}\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\3\uparrow 3\end{matrix}}\right\}\ 27$$

что намного больше числа Грэма, поскольку число $3\rightarrow 3\rightarrow 27\rightarrow 2$ $=f^{27}(1)$ намного больше, чем $65$.

функция компьютерной графики

Конвей и Гай создали простую функцию с одним аргументом, которая диагонализует все обозначения, определяемую как:

$cg(n)=\underbrace {n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n} _{n}$

то есть последовательность такая:

$cg(1)=1$

$cg(2)=2\to 2=2^{2}=4$

$cg(3)=3\to 3\to 3=3\uparrow \uparrow \uparrow 3$

$cg(4)=4\to 4\to 4\to 4$

$cg(5)=5\to 5\to 5\to 5\to 5$

...

Эта функция, как и следовало ожидать, растет необычайно быстро.

Питера

Питер Херфорд, веб-разработчик и статистик, определил расширение этой записи:

$a\rightarrow _{b}c=\underbrace {a\rightarrow _{b-1}a\rightarrow _{b-1}a\rightarrow _{b-1}\dots \rightarrow _{b-1}a\rightarrow _{b-1}a\rightarrow _{b-1}a} _{c{\text{ arrows}}}$

$a\rightarrow _{1}b=a\rightarrow b$

В остальном все обычные правила остаются неизменными.

$a\rightarrow _{2}(a-1)$ уже равен вышеупомянутому $cg(a)$, и функция $f(n)=n\rightarrow _{n}n$ растет гораздо быстрее, чем компания Конвея и Гая. $cg(n)$.

Обратите внимание, что выражения типа $a\rightarrow _{b}c\rightarrow _{d}e$ являются незаконными, если $b$ и $d$ это разные числа; цепочка должна иметь только один тип стрелки вправо.

Однако, если мы немного изменим это так, что:

$a\rightarrow _{b}c\rightarrow _{d}e=a\rightarrow _{b}\underbrace {c\rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}\dots \rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}c} _{e{\text{ arrows}}}$

тогда не только $a\rightarrow _{b}c\rightarrow _{d}e$ становятся законными, но обозначения в целом становятся намного сильнее.

См. также

• Обозначения Штейнгауза – Мозера
• Систематическое создание все более быстро возрастающих последовательностей

Внешние ссылки

• Фактоиды > большие цифры
• Большие числа Роберта Мунафо
• Книга чисел Дж. Х. Конвея и Р. К. Гая