コンウェイ連鎖矢印記法

Means of expressing certain extremely large numbers

数学者ジョン・ホートン・コンウェイによって考案されたコンウェイ連鎖矢印表記法は、特定の非常に大きな数を表現する方法です。^{[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}$

プロパティ

長さが 1 以上であるサブチェーンを表します。 ${\displaystyle X,Y}$

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番目の規則は核心です。4つ以上の要素が2以上の値で終わる連鎖は、同じ長さの連鎖になりますが、最後から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 a}$

${\displaystyle =2[\uparrow ^{a}]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による）

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

体系的な例

4 つの項（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 (n+3)\to (m-2))-3}$for (ハイパーオペレーションなので) ${\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}$

証明:まず中間関数 を定義します。これを使ってグラハム数を と定義できます。(上付き文字の 64 は関数のべき乗を表します。) ${\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)}$

ルール 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}$

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

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

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

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

CG機能

Conway と Guy は、次のように定義される、表記全体を対角化する単純な単一引数関数を作成しました。

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

...

この関数は、予想どおり、非常に速く成長します。

ピーター・ハーフォードによる拡張

ウェブ開発者であり統計学者でもある Peter Hurford 氏は、この表記法の拡張を定義しました。

${\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)}$はすでに前述の と等しく、関数はConway と Guy の よりもはるかに速く増加します。 ${\displaystyle cg(a)}$ ${\displaystyle f(n)=n\rightarrow _{n}n}$ ${\displaystyle cg(n)}$

と が異なる数値の場合、のような式は無効であることに注意してください。チェーンには右矢印の種類が 1 つだけ含まれている必要があります。 ${\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}}}}$

そうすれば、合法になるだけでなく、表記法全体がより強力になります。^[2] ${\displaystyle a\rightarrow _{b}c\rightarrow _{d}e}$

参照

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

参考文献

1. ジョン・H・コンウェイ＆リチャード・K・ガイ『民数記』1996年、59-62ページ
2. “Large Numbers, Part 2: Graham and Conway - Greatplay.net”. archive.is . 2013年6月25日. 2013年6月25日時点のオリジナルよりアーカイブ。 2018年2月18日閲覧。

外部リンク

• 豆知識 > 大きな数字
• ロバート・ムナフォの「Large Numbers」
• JHコンウェイとRKガイ著『民数記』

Retrieved from "https://en.wikipedia.org/w/index.php?title=Conway_chained_arrow_notation&oldid=1319423617"