コンウェイ連鎖矢印記法

数学者ジョン・ホートン・コンウェイによって考案されたコンウェイ連鎖矢印記法は、非常に大きな数を表現する手段である。^{[ 1 ]}これは単に右向きの矢印で区切られた正の整数の有限列である。例：${\displaystyle 2\to 3\to 4\to 5\to 6}$。

ほとんどの組み合わせ表記法と同様に、この定義は再帰的です。この場合、表記法は最終的に、最も左にある数を（通常は非常に大きな）整数乗したものに解決されます。

「コンウェイ・チェーン」は次のように定義されます。

• 任意の正の整数は長さの鎖である${\displaystyle 1}$。
• 長さの鎖${\displaystyle n}$、右矢印 → と正の整数が続くと、長さのチェーンが形成されます。${\displaystyle n+1}$。

以下の6つの規則に従って、どの連鎖も整数を表します。2つの連鎖が同じ整数を表す場合、それらは同等であると言われます。

させて${\displaystyle a,b,c}$正の整数を表すとし、${\displaystyle \#}$チェーンの残りの部分を変更せずに表す。すると：

1. 空のチェーン（または長さのチェーン）${\displaystyle 0}$) は${\displaystyle 1}$。
2. チェーン${\displaystyle a}$数を表す${\displaystyle a}$。
3. チェーン${\displaystyle a\rightarrow b}$数を表す${\displaystyle a^{b}}$。
4. チェーン${\displaystyle a\rightarrow b\rightarrow c}$数を表す${\displaystyle a\uparrow ^{c}b}$（クヌースの上向き矢印表記を参照）
5. 鎖${\displaystyle \#\rightarrow 1}$そして${\displaystyle \#\rightarrow 1\rightarrow a}$チェーンと同じ数を表す${\displaystyle \#}$
6. そうでなければ、チェーン${\displaystyle \#\rightarrow (a+1)\rightarrow (b+1)}$チェーンと同じ番号を表します${\displaystyle \#\rightarrow (\#\rightarrow a\rightarrow (b+1))\rightarrow b}$。

させて${\displaystyle X,Y}$長さが1以上のサブチェーンを表す。

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)}$

矢印チェーンは全体として扱うように注意する必要があります。矢印チェーンは、二項演算子の反復適用を表すものではありません。他の中置記号のチェーン（例：3  +  4  +  5  +  6  + 7）は、意味を変えることなく 断片（例：（3  +  4） +  5  +  （6  + 7））で考えることがよくあるのに対し（結合法則を参照）、少なくとも右から左へ 3 ^{4 5 6 7}のように所定の順序で段階的に評価できますが、コンウェイの矢印チェーンではそうではありません。 

例えば：

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

6番目の定義ルールが核心です。2以上の要素で終わる4つ以上の要素の連鎖は、同じ長さで最後から2番目の要素が（通常ははるかに）大きい連鎖と等しくなります。しかし、最後の要素は減少し、最終的に5番目のルールによって連鎖が短縮されます。その後、クヌースの言葉を借りれば「多くの詳細」を経て、連鎖は3つの要素に縮小され、4番目のルールによって再帰が終了します。

例はすぐにかなり複雑になります。以下に簡単な例をいくつか示します。

${\displaystyle n}$

${\displaystyle =n}$（規則2による）

${\displaystyle p\to q}$

${\displaystyle =p^{q}}$（規則3による）

したがって、${\displaystyle 3\to 4=3^{4}=81}$

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

${\displaystyle =4\uparrow \uparrow 3}$（規則4による）

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

${\displaystyle =2[\uparrow ^{2}]2}$（規則4による）

${\displaystyle =4}$（クヌースの上向き矢印表記を参照）

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

${\displaystyle =2\uparrow \uparrow \uparrow 4}$（規則4による）

${\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 \approx \exp _{10}^{65533}(4.29508)}$

（テトラションを参照）

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

${\displaystyle =2\to 3\to (2\to 3)\to 1}$ （規則6による）

${\displaystyle =2\to 3\to 8\to 1}$ （規則3による）

${\displaystyle =2\to 3\to 8}$（規則5による）

${\displaystyle =2\to (2\to 2\to 8)\to 7}$（規則6による）

${\displaystyle =2\to 4\to 7}$（規則6による）

${\displaystyle =2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 4}$（規則4による）

=前の数値よりはるかに大きい

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

${\displaystyle =3\to 2\to (3\to 2)\to 1}$（規則6による）

${\displaystyle =3\to 2\to 9\to 1}$（規則3による）

${\displaystyle =3\to 2\to 9}$（規則5による）

${\displaystyle =3\to 3\to 8}$（規則6による）

${\displaystyle =3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3}$（規則4による）

=前の数値よりはるかに大きい

アッカーマン関数は、コンウェイ連鎖矢印記法を用いて表現できる。

${\displaystyle A(m,n)=(2\to (n+3)\to (m-2))-3}$のために${\displaystyle m\geq 3}$（以来${\displaystyle A(m,n)=2[m](n+3)-3}$（ハイパーオペレーション中）

したがって

${\displaystyle 2\to n\to m=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 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}}}$$

fは厳密に増加するので、

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

これは与えられた不等式です。

連鎖矢印を使用すると、例えばグラハム数よりもはるかに大きな数を指定するのは非常に簡単です。${\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\}\ 27}$$ これはグラハムの数よりもはるかに大きい。なぜならその数は${\displaystyle 3\rightarrow 3\rightarrow 27\rightarrow 2}$${\displaystyle =f^{27}(1)}$よりはるかに大きい${\displaystyle 65}$。

コンウェイとガイは、表記全体を対角化する、引数が1つのシンプルな関数を作成しました。それは次のように定義されます。

${\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}$これらは異なる数字です。チェーンには右向き矢印が1種類しかあってはなりません。

しかし、これを少し修正して次のようにすると：

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

• シュタインハウス・モーザー記法
• ますます速い増加シーケンスを体系的に作成する

• 豆知識>大きな数字
• ロバート・ムナフォの大きな数字
• JHコンウェイとRKガイによる『数字の書』