Обозначение стрелок Конвея - Conway chained arrow notation

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

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

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

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

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

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

Если ${\displaystyle p}$, ${\displaystyle q}$, и ${\displaystyle r}$ положительные целые числа, и ${\displaystyle X}$ является подсистемой, то:

1. Пустая цепочка (или цепочка длины 0) равна ${\displaystyle 1}$, а цепочка ${\displaystyle p}$ представляет собой число ${\displaystyle p}$.
2. ${\displaystyle X\to 1}$ эквивалентно ${\displaystyle X}$.
3. ${\displaystyle p\rightarrow q\rightarrow r}$ эквивалентно ${\displaystyle p[\uparrow ^{r}]q}$. (видеть Обозначение стрелки Кнута вверх )
4. ${\displaystyle X\to p\to (q+1)}$ эквивалентно ${\displaystyle X\to (X\to (\cdots (X\to (X)\to q)\cdots )\to q)\to q}$
   (с ${\displaystyle p}$ копии ${\displaystyle X}$, ${\displaystyle p-1}$ копии ${\displaystyle q}$, и ${\displaystyle p-1}$ пары скобок; подает заявку на ${\displaystyle q}$ > 0).
5. Потому что ${\displaystyle p\rightarrow q\rightarrow 1}$ эквивалентно ${\displaystyle p\to q}$, (По правилу 2), а также ${\displaystyle p\uparrow q}$ = ${\displaystyle p^{q}}$, (По правилу 3) можно определить ${\displaystyle p\to q}$ в равной ${\displaystyle p^{q}}$

Обратите внимание, что четвертое правило можно заменить повторным применением двух правил, чтобы избежать эллипсы:

4а. ${\displaystyle X\to 1\to (q+1)}$ эквивалентно ${\displaystyle X}$

4b. ${\displaystyle X\to (p+1)\to (q+1)}$ эквивалентно ${\displaystyle X\to (X\to p\to (q+1))\to q}$

Характеристики

1. Цепь оценивает абсолютную степень своего первого числа
2. Следовательно, ${\displaystyle 1\to Y}$ равно ${\displaystyle 1}$
3. ${\displaystyle X\to 1\to Y}$ эквивалентно ${\displaystyle X}$
4. ${\displaystyle 2\to 2\to Y}$ равно ${\displaystyle 4}$
5. ${\displaystyle X\to 2\to 2}$ эквивалентно ${\displaystyle X\to (X)}$ (не путать с ${\displaystyle X\to X}$)

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

Осторожно обращаться с цепочкой стрел в целом. Цепочки стрелок не описывают повторное применение бинарного оператора. В то время как цепочки других инфиксных символов (например, 3 + 4 + 5 + 6 + 7) часто можно рассматривать фрагментами (например, (3 + 4) + 5 + (6 + 7)) без изменения значения (см. ассоциативность ), или, по крайней мере, можно оценивать шаг за шагом в установленном порядке, например 3⁴⁵⁶⁷ справа налево, это не так с цепями стрел Конвея.

Например:

• ${\displaystyle 2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=16}$
• ${\displaystyle 2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^{3^{2}}=512}$
• ${\displaystyle \left(2\rightarrow 3\right)\rightarrow 2=\left(2^{3}\right)^{2}=64}$

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

Примеры

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

${\displaystyle n}$

${\displaystyle =n}$ (По правилу 1)

${\displaystyle p\to q}$

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

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

${\displaystyle 4\to 3\to 2}$

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

${\displaystyle =4\uparrow (4\uparrow 4)}$

${\displaystyle =4\uparrow 256}$

${\displaystyle =4^{256}}$

${\displaystyle =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,}$ ${\displaystyle 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}$

${\displaystyle \approx 1.34*10^{154}}$

${\displaystyle 2\to 2\to a}$

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

${\displaystyle =4}$ (видеть Обозначение стрелки Кнута вверх )

${\displaystyle 2\to 4\to 3}$

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

${\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow 4)}$

${\displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow (2\uparrow 2)))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow 4))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow 16)}$

${\displaystyle =2\uparrow \uparrow (65536)}$

${\displaystyle ={^{65536}2}}$ (видеть тетрация )

${\displaystyle 2\to 3\to 2\to 2}$

${\displaystyle =2\to 3\to (2\to 3)\to 1}$ (По правилу 4)

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

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

${\displaystyle =2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3}$ (По правилу 3)

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

${\displaystyle 3\to 2\to 2\to 2}$

${\displaystyle =3\to 2\to (3\to 2)\to 1}$ (По правилу 4)

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

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

${\displaystyle =3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 2}$ (По правилу 3)

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

Систематические примеры

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

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

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

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

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

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

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

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

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

Снова мы можем обобщить. Когда мы пишем ${\displaystyle g_{q}(p)=X\to p\to q}$ у нас есть ${\displaystyle X\to p\to q+1=g_{q}^{p}(1)}$, то есть, ${\displaystyle g_{q+1}(p)=g_{q}^{p}(1)}$. В приведенном выше случае ${\displaystyle g_{2}(p)=a\to b\to p\to 2=f^{p}(1)}$ и ${\displaystyle g_{3}(p)=g_{2}^{p}(1)}$, так ${\displaystyle 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)}$

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

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

${\displaystyle A(m,n)=2\to (m-2)\to (n+3)-3}$ за ${\displaystyle m>2}$ (С ${\displaystyle A(m,n)=2[m](n+3)-3}$ в гипероперация )

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

${\displaystyle 2\to m\to n=A(m+2,n-3)+3}$ за ${\displaystyle n>2}$

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

Число Грэма

Число Грэма ${\displaystyle G}$ сам по себе не может быть кратко выражен в обозначении цепной стрелки Конвея, но он ограничен следующим:

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2}$

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

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

${\displaystyle f^{64}(1)}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))}$ (с 64 ${\displaystyle 3\rightarrow 3}$s)

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1}$

${\displaystyle =3\rightarrow 3\rightarrow 64\rightarrow 2;}$

$${\displaystyle \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}}}$$

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

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))}$ (с 64 ${\displaystyle 3\rightarrow 3}$s)

$${\displaystyle \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}}}$$

${\displaystyle f^{64}(27)}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))}$ (с 64 ${\displaystyle 3\rightarrow 3}$s)

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))}$ (с 65 ${\displaystyle 3\rightarrow 3}$s)

${\displaystyle =3\rightarrow 3\rightarrow 65\rightarrow 2}$ (вычисления, как указано выше).

${\displaystyle =f^{65}(1)}$

$${\displaystyle \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}}}$$

С ж является строго возрастающий,

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

что и есть данное неравенство.

С помощью связанных стрелок очень легко указать число, намного большее, чем ${\displaystyle G}$, Например, ${\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3}$.

${\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,}$

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

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

$${\displaystyle \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\}\ 3\uparrow 3={\text{27 layers}}}$$

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

Функция CG

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

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

это означает, что последовательность:

${\displaystyle cg(1)=1}$

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

${\displaystyle cg(3)=3\to 3\to 3=3\uparrow \uparrow \uparrow 3}$

${\displaystyle cg(4)=4\to 4\to 4\to 4}$

${\displaystyle cg(5)=5\to 5\to 5\to 5\to 5}$

...

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

Расширение Питера Херфорда

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

${\displaystyle 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}}}}$

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

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

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

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

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

${\displaystyle 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}}}}$

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

Смотрите также

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

Рекомендации

1. Джон Х. Конвей и Ричард К. Гай, Книга чисел, 1996, стр.59-62
2. «Большие числа, часть 2: Грэм и Конвей - Greatplay.net». archive.is. 2013-06-25. Архивировано из оригинал на 2013-06-25. Получено 2018-02-18.

внешняя ссылка

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