コンウェイのチェーン表記

コンウェイのチェーン表記（コンウェイのチェーンひょうき、テンプレート:Lang-en-short）とは、1995年にイギリスの数学者ジョン・ホートン・コンウェイによって導入された巨大数の表記法の一つである。

クヌースの矢印表記やアッカーマン関数などより比較的強い演算である。具体的には、3つ組ではクヌースの矢印表記と等価だが、更に長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数を表すことができる。

導入

加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって テンプレート:Math と表して、さらに テンプレート:Math の反復を テンプレート:Math（テトレーション）、テンプレート:Math の反復を テンプレート:Math（ペンテーション）、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。

$\begin{array}{ccccc}(1)a\times b& =& \underset{b\text{ copies of }a}{\underbrace{a+a+\cdots +a}}& =& \underset{b-1}{\underbrace{a+\cdots a+}}a\\ (2)a\uparrow b& =& \underset{b\text{ copies of }a}{\underbrace{a\times a\times \cdots \times a}}& =& \underset{b-1}{\underbrace{a\times \cdots a\times }}a\\ (3)a{\uparrow }^{c}b& =& \underset{b\text{ copies of }a}{\underbrace{a{\uparrow }^{c-1}a{\uparrow }^{c-1}\cdots {\uparrow }^{c-1}a}}& =& \underset{b-1}{\underbrace{a{\uparrow }^{c-1}\cdots a{\uparrow }^{c-1}}}a& =& a\underset{b-1\text{ copies of }a}{\underbrace{{\uparrow }^{c-1}a\cdots {\uparrow }^{c-1}a}}\end{array}$

コンウェイのチェーン表記は、このクヌースの矢印表記の一般化、拡張である。以下チェーンの各項はすべて自然数であるものとする。

コンウェイはまず長さが テンプレート:Math のチェーンを、クヌースの矢印表記を用いて次のように与えた。

$(4)a\to b\to c=a\underset{c\text{本}}{\underbrace{\uparrow \cdots \uparrow }}b=a{\uparrow }^{c}b$($a\to b=a^b$とも書き換えられる)

このチェーンによって テンプレート:Math を書き換えると次のような式になる。これは末尾 テンプレート:Math のチェーンを末尾 テンプレート:Math のチェーンに分解する式となっている。

$(5)\begin{array}{cc}a\to b\to c=& \underset{b\text{ copies of }a}{\underbrace{a{\uparrow }^{c-1}a{\uparrow }^{c-1}\cdots a{\uparrow }^{c-1}a{\uparrow }^{c-1}a{\uparrow }^{c-1}a}}=a{\uparrow }^{c-1}\underset{b-1\text{ copies of }a}{\underbrace{a{\uparrow }^{c-1}a{\uparrow }^{c-1}\cdots a{\uparrow }^{c-1}a{\uparrow }^{c-1}a{\uparrow }^{c-1}a}}=a{\uparrow }^{c-1}a{\uparrow }^c(b-1)=a{\uparrow }^{c-1}\{a\to (b-1)\to c\}\\ =& a\to \{a\to (b-1)\to c\}\to (c-1)=\underset{b}{\underbrace{a\to (a\to (\cdots \to (a\to (a}}\underset{b-1}{\underbrace{)\to (c-1))\to \cdots )\to (c-1))\to (c-1)}}\end{array}$

この式の テンプレート:Mvar を部分チェーン テンプレート:Mvar に置き換えることで、長さが テンプレート:Math 以上のチェーンに対する式が得られる。

$(6)X\to b\to c=X\to \{X\to (b-1)\to c\}\to (c-1)=\underset{b}{\underbrace{X\to (X\to (\cdots \to (X\to (X}}\underset{b-1}{\underbrace{)\to (c-1))\to \cdots )\to (c-1))\to (c-1)}}$

さらにコンウェイはチェーン末尾のテンプレート:Mathは無視されるとした。従って式 テンプレート:Math, テンプレート:Math を繰り返して末項を テンプレート:Math にすることで、長さが テンプレート:Math 短いチェーンへと分解することができる。

$(7)a_1\to \cdots \to a_n\to 1=a_1\to \cdots \to a_n$

また、この規則から長さが テンプレート:Math のチェーンは累乗となる。

さらにコンウェイはチェーン途中のテンプレート:Mathの右側の全ても無視されるとした。それにより4つ組チェーンの計算も行える。

$a\to b\to \cdot \cdot \cdot \to z\to 1\to \cdot \cdot \cdot =a\to b\to \cdot \cdot \cdot \to z$

定義

次のようにチェーンを定義する。

• 任意の正の整数は、長さ テンプレート:Math のチェーンである。
• 長さ テンプレート:Mvar のチェーンに、右向き矢印 テンプレート:Math と正の整数を繋げたものは、長さ テンプレート:Math のチェーンとなる。

さらに テンプレート:Math を正の整数、テンプレート:Mvar を部分チェーンとするとき、チェーンについて以下が成り立つ。

• 長さ テンプレート:Math のチェーン（空チェーン）は、テンプレート:Math に等しい。
• 長さ テンプレート:Math のチェーン テンプレート:Mvar は、テンプレート:Mvar に等しい。
• 長さ テンプレート:Math のチェーン テンプレート:Math は、テンプレート:Math に等しい。
• 長さ テンプレート:Math のチェーン テンプレート:Math は テンプレート:Math に、テンプレート:Math は テンプレート:Math に各々等しい。
• テンプレート:Math は テンプレート:Mvar に等しい。即ちチェーン右端の テンプレート:Math は取り除くことができる。
• テンプレート:Math は テンプレート:Mvar に等しい。即ちチェーン右端の テンプレート:Math は取り除くことができる。
• テンプレート:Math は $X\to \{X\to p\to (q+1)\}\to q$ に等しい。

ここで関数 テンプレート:Mvar を テンプレート:Math とおくと、最後の二つの条件は次のようにも述べられる。但し テンプレート:Math は テンプレート:Mvar の テンプレート:Mvar 回反復合成である。

$\begin{array}{cc}X\to (p+1)\to (q+1)& =\underset{p}{\underbrace{X\to (\cdots \to (X\to (}}X\underset{p}{\underbrace{)\to q)\to \cdots )\to q}}\\ & =\underset{p}{\underbrace{f(\cdots f(}}X\underset{p}{\underbrace{)\cdots )}}\\ & =f^p(X)\end{array}$

別の定義

上記以外の書き方でされている定義もある。

書き方は違うが、意味は同じである。

以下の4つの定義でチェーン表記を定義することも可能である。

チェーン表記$a\to b\to c\to \dots \to y\to z$(a~zは正の整数)を以下のように定義する。

• $a\to b=a^b$
• $a\to b\to c\to \dots \to y\to z\to 1=a\to b\to c\to \dots \to y\to z$
• $a\to b\to c\to \dots \to y\to z\to 1\to \dots =a\to b\to c\to \dots \to y\to z$

• $a\to b\to c\to \dots \to y\to z=a\to b\to c\to \dots \to (a\to b\to c\to \dots \to (y-1)\to z)\to (z-1)$

性質

以下、項（正の整数）を小文字 テンプレート:Math 、チェーン（および部分チェーン）を大文字 テンプレート:Math で表す。

• 長さ テンプレート:Math のチェーンは、ハイパー演算子、クヌースの矢印表記、および配列表記による表示をもつ。
  • $p\to q\to r=H_{r+2}(p,q)$
  • $p\to q\to r=p{\uparrow }^{r}q$
  • $p\to q\to r=\{p,q,r\}$
• 任意のチェーンに対し常にただ一つの整数が定まる。
• 長さ テンプレート:Math のチェーン テンプレート:Math は適当な テンプレート:Math によって テンプレート:Math と変形できる。即ち先頭から テンプレート:Math 項を保ったまま長さを テンプレート:Math 短くできる。
• テンプレート:Math から始まるチェーン テンプレート:Math は テンプレート:Math の冪 テンプレート:Math となる。
• テンプレート:Math から始まるチェーン テンプレート:Math は テンプレート:Math に等しい。
• テンプレート:Math より後の項はすべて無視することができる。
  • $X\to 1\to Y=X$
• 先頭に テンプレート:Math が連なったチェーン テンプレート:Math は テンプレート:Math に等しい。
• 末尾に テンプレート:Math が連なったチェーン テンプレート:Math は テンプレート:Math に等しい。
• テンプレート:Math は テンプレート:Math に等しい。
• テンプレート:Math は テンプレート:Math に等しい。
• テンプレート:Math は テンプレート:Math に等しい。

例

以下は長さが テンプレート:Math のチェーンの計算例である。

• テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

• テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

• テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

テンプレート:Math

以下は長さが テンプレート:Math のチェーンのクヌースの矢印表記による展開例(縦横展開)である。

$\begin{array}{ccc}p\to q\to r\to 1& =& p\underset{r\text{本}}{\underbrace{\uparrow \cdots \uparrow }}q\end{array}$

$\begin{array}{ccc}p\to q\to r\to 2=p\to q\to \{p\to q\to (r-1)\to 2\}\to 1=p\to q\to \{p\to q\to (r-1)\to 2\}=\underset{r}{\underbrace{p\to q\to (p\to q\to \cdots (p\to q\to (}}1)\underset{r}{\underbrace{\to 1)\cdots \to 1)}}& =& p\underset{p\underset{\underset{p\underset{p^q\text{本}}{\underbrace{\uparrow \cdots \uparrow }}q\text{本}}{\underbrace{⋮}}}{\underbrace{\uparrow \cdots \cdots \uparrow }}q\text{本}}{\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow }}q\end{array}\}r\text{層}$

$\begin{array}{ccc}p\to q\to r\to 3=\underset{r}{\underbrace{p\to q\to (p\to q\to \cdots (p\to q\to (}}1)\underset{r}{\underbrace{\to 2)\cdots \to 2)}}& =& \\ & & \\ & & \\ & & \\ & & \\ & & \\ & & \end{array}\underset{r}{\underbrace{\begin{array}{c}p\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow }q\\ p\underbrace{\uparrow \cdots \cdots \uparrow }q\text{本}\\ ⋮\\ ⋮\\ \underset{p\underset{p^q\text{本}}{\underbrace{\uparrow \cdots \uparrow }}q\text{本}}{\underbrace{⋮}}\end{array}\}\begin{array}{c}p\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow }q\text{層}\\ p\underbrace{\uparrow \cdots \cdots \uparrow }q\text{本}\\ ⋮\\ \underset{p\underset{p^q\text{本}}{\underbrace{\uparrow \cdots \uparrow }}q\text{本}}{\underbrace{⋮}}\end{array}\}\cdots \left\}\begin{array}{c}p\underset{p\underset{\underset{p\underset{p^q\text{本}}{\underbrace{\uparrow \cdots \uparrow }}q\text{本}}{\underbrace{⋮}}}{\underbrace{\uparrow \cdots \cdots \uparrow }}q\text{本}}{\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow }}q\text{層}\end{array}\right\}{p}^q\text{層}}}$

アッカーマン関数

アッカーマン関数はコンウェイのチェーン表記へ置き換えられる:

m > 2の際 A(m, n) = (2 → (n + 3) → (m − 2)) − 3 （ハイパー演算の角括弧表記を用いると A(m, n) = 2 [m] (n + 3) - 3）

よって

n > 2の際 2 → n → m = A(m + 2,n − 3) + 3

(n = 1 と n = 2 は A(m, −2) = −1 と A(m, −1) = 1に対応し、論理的に加算できる。)

グラハム数

グラハム数 $G$ それ自体を、コンウェイのチェーン表記を用いて簡潔に表す事は出来ない。しかし、仲介させる関数を $g(n)=3\to 3\to n=\begin{array}{c}3\underbrace{\uparrow \uparrow \cdots \uparrow }3\\ \text{n 本 の 矢 印}\end{array}$ と定義することで $G=g^{64}(4)$ と表記できる。(写像の冪を参照。)又、 $3\to 3\to 64\to 2<G<3\to 3\to 65\to 2$ である。

コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。

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

$=3\to 3\to (3\to 3\to 27\to 2)\to 2$

$=g^{3\to 3\to 27\to 2}(1)$

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

$\begin{array}{cc}=& 3\underset{}{\underbrace{\uparrow \uparrow \uparrow \cdots \cdots \cdots \cdot \cdot \uparrow \uparrow \uparrow }}3\\ & 3\underset{}{\underbrace{\uparrow \uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow \uparrow \uparrow }}3\text{本}\\ & 3\underset{}{\underbrace{\uparrow \uparrow \uparrow \cdots \cdots \cdots \uparrow \uparrow \uparrow }}3\text{本}\\ & \underbrace{⋮}\\ & 3\underset{3\uparrow 3\text{本}}{\underbrace{\uparrow \uparrow \uparrow \cdots \cdot \uparrow \uparrow \uparrow }}3\text{本}\end{array}\}\begin{array}{c}3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow }3\text{層 }\\ 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \uparrow }3\text{本}\\ \underbrace{⋮}\\ 3\underset{3\uparrow 3\text{本}}{\underbrace{\uparrow \uparrow \cdots \cdot \uparrow }}3\text{本}\end{array}\}3\uparrow 3=27\text{層 }$

数$3\to 3\to 27\to 2=g^{27}(1)$ は65よりもはるかに大きいので、$3\to 3\to 3\to 3$はグラハム数よりはるかに大きい。 さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。$3\to 3\to 3\to 3$はコンウェイのテトラトリと呼ばれる。

CG関数

コンウェイとテンプレート:仮リンクに共同制作された単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:

$cg(n)=\underset{\text{長 さ }n}{\underbrace{n\to n\to n\to \dots \to n\to n\to n}}$

その出力を順に並べると:

この関数は予測されるように、とても急速に増大する。

この関数は急増加関数で$cg(x)\approx f_{{\omega }^2}(x)$と近似できる。

拡張チェーン系の表記

このチェーン表記にも、次のような拡張表記が考案されている。

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

Webデベロッパーで統計学者のピーター・ハーフォードは、2011年にこの表記法の拡張を定義した。

$a{\to }_{b}c=\underset{c\text{ 本 の 矢}}{\underbrace{a{\to }_{b-1}a{\to }_{b-1}a{\to }_{b-1}\dots {\to }_{b-1}a{\to }_{b-1}a{\to }_{b-1}a}}$（あくまで${\to }_{b-1}$が$c$本、という意味）

$a{\to }_2(a-1)$は既に cg(a) と同等であり、関数$f(n)=n{\to }_{n}n$は cg(n) よりも大きな増加速度を持つ。

定義

$a{\to }_{1}b$$=$$a^b$

$a{\to }_{1}b{\to }_{1}n$$=$$a{\uparrow }^{n}b$

$a{\to }_{n}b{\to }_{n}c\dots {\to }_{n}z{\to }_{n}1$$=$$a{\to }_{n}b{\to }_{n}c\dots {\to }_{n}z$

$a{\to }_{n}b{\to }_{n}c\dots {\to }_{n}z{\to }_{n}1{\to }_n\dots$$=$$a{\to }_{n}b{\to }_{n}c\dots {\to }_{n}z$

$a{\to }_{n}b{\to }_n\dots {\to }_{n}y{\to }_{n}z$$=$$a{\to }_{n}b{\to }_n\dots {\to }_n(a{\to }_{n}b{\to }_n\dots (y-1){\to }_{n}z){\to }_n(z-1)$

$a{\to }_{n}b=\underset{\text{長 さ}b+1}{\underbrace{a{\to }_{n-1}a{\to }_{n-1}\dots {\to }_{n-1}a}}$

この表記は拡張チェーン表記と呼ばれ、同じ拡張チェーン系の回転矢印表記と同じくらいの強さである。歴史的には、回転矢印表記が先に考案され、後にそれとは独立にこのハーフォードの拡張チェーン表記が考案されたが、現在ではチェーン表記の拡張としてはより定義や記述がすっきりしているこのハーフォード式が標準的となっている。もっとも、拡張チェーン系表記のレベルの巨大数は、巨大数論的に中途半端なポジションということもあり、そのレベルの巨大数を表す場合は拡張チェーン系表記より強力な配列表記（海外）あるいは多変数アッカーマン関数（日本）を用いるのが最も主流となっている。

この表記は急増加関数で$x{\to }_{x}x\approx f_{{\omega }^3}(x)$と近似できる。

ちなみに多変数アッカーマン関数で$x{\to }_{x}x\approx A(1,0,0,0,x)$程度である。

彼は上記以外の規則は変更しなかった。（一つのチェーンにおいては1種類の矢印のみを使用できた。つまりb≠dの際$a{\to }_{b}c{\to }_{d}e$は規則違反になる）

もし更に規則を若干訂正し

$a{\to }_{b}c{\to }_{d}e=a{\to }_b\underset{e\text{ 本 の 矢}}{\underbrace{c{\to }_{d-1}c{\to }_{d-1}c{\to }_{d-1}\dots {\to }_{d-1}c{\to }_{d-1}c{\to }_{d-1}c}}$

とすると、$a{\to }_{b}c{\to }_{d}e$は規則違反では無くなる上に表記法が更に強くなる(あまり意味はない。つまり、本質的に大きくする手段は別にある。)。

クリス・バードによる拡張（回転矢印表記）

矢印表記やチェーン表記の拡張版として、クリス・バード(Chris Bird)によって考案された回転矢印表記というものもある。この表記法ではその矢印の回転を繰り返すことにより、非拡張チェーンを遥かに超える巨大な数が表記可能となる。これは2chの巨大数スレッドで一時期ある程度使われたことがある。ただしこれは発想こそ単純であるものの、ピーター・ハーフォードの拡張チェーン表記とほぼ同等の増加速度であり、それと比べると若干定義が複雑なことと、配列表記の方が効率的に数の大きさを爆発させることができることもあり、近年ではこの回転矢印表記が用いられることはほとんどなくなっている。

その他

その他の拡張チェーン系の表記としては、次のようなものが考えられている。

• チェーンを角括弧で括り、[a→b]_nのように拡張レベルを角括弧の外に書いて、2変数の場合の右側の数bを1つ下のレベルのチェーンのaの個数とするAeton式

更に、ハーフォード式・バード式（回転矢印表記）・Aeton式の三者よりも強力な表記として、

• 拡張レベルを多変数化して例えば3[3,1,2]3[3,1,2]3などのように書く配列チェーン表記
• ハーフォード式と同じように矢印に添字を付ける→_nという表記を使いながら、添字が揃っていなくても計算でき、かつレベルの違いを活かして強くした混合チェーン表記

その他

チェーン表記（およびその拡張表記）では、数の大きさを評価するための重要度は次の通りである：

（拡張チェーン系の表記におけるチェーンの拡張レベル＞）チェーンの長さ＞末尾の変数＞末尾から2番目の変数＞それ以外の変数

チェーン表記（およびその拡張表記）では、どの変数の値が増えても厳密には数は増えるものの、特に5つ組以上のチェーンでは、末尾の2つ以外の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。また末尾の変数が巨大数レベルになれば、末尾から2番目の変数の値が増えても巨大数として無視できるレベルの増加にしかならない。

ふぃっしゅ数バージョン1はCG関数でCG(グラハム数)、つまり$\underset{\text{グ ラ ハ ム 数 個 の G}}{\underbrace{G\to G\to \dots \to G}}$より遥かに大きい。ふぃっしゅ数バージョン1はピーター・ハーフォードの拡張チェーン表記による近似で≒5→₂64→₂2、ふぃっしゅ数バージョン2は同表記による近似で≒3→₆₄3→₆₄2程度の大きさとなる。このようにふぃっしゅ数はバージョン1とバージョン2までは、拡張チェーン系の表記の範囲で近似可能であるが、バージョン3以上になるとそのレベルをも遥かに本質的に超えてしまう。

チェーン表記とは異なった規則により、チェーン表記（およびその拡張表記）よりも効率的に数の大きさを爆発させることができる表記として、配列表記があり、それにも拡張表記が考案されており、その最終形態にはBEAFとバードの配列表記がある。具体的には、チェーン表記で表される数は多変数アッカーマン関数では3変数程度で配列表記では4変数程度、ピーター・ハーフォードの拡張チェーン表記（あるいはクリス・バードの回転矢印表記）で表される数は多変数アッカーマン関数では4変数程度で配列表記では5変数程度のレベルとなる。チェーン表記およびその拡張表記と配列表記との比較（近似・大小関係）については配列表記#チェーン表記との比較および回転矢印表記#他表記との比較を参照のこと。

BEAFの配列表記は多変数アッカーマン関数と同じくらいの増加速度を持ち、BEAFそのものはさらに大きい増加速度を持つ（テトレーション配列など）。

参考文献

• http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm テンプレート:En icon
• http://home.earthlink.net/~mrob/pub/math/largenum-4.html テンプレート:En icon

関連項目

• 巨大数
• クヌースの矢印表記
• 配列表記