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

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

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

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

: \begin{array}{lclcl}
 (1)\qquad
 a \times b
 &=& \underbrace{ a + a + \cdots + a }_{b\text{ copies of }a}
 &=& \underbrace{
  a +
  \cdots
  a \,+
 }_{b-1} ~a
\\
 (2)\qquad
 a \uparrow b
 &=& \underbrace{ a \times a \times \cdots \times a }_{b\text{ copies of }a}
 &=& \underbrace{
  a \times
  \cdots
  a \,\times
 }_{b-1} ~a
\\
 (3)\qquad
 a \uparrow^c b
 &=& \underbrace{ a \uparrow^{c-1} a \uparrow^{c-1} \cdots \uparrow^{c-1} a }_{b\text{ copies of }a}
 &=& \underbrace{
  a \uparrow^{c-1}
  \cdots
  a \uparrow^{c-1}
 }_{b-1} ~a
 &=& a ~ \underbrace{
  \uparrow^{c-1} a
  \cdots
  \uparrow^{c-1} a}_{b-1\text{ copies of }a}
\end{array} \,\!

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

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

: (4)\qquad a \rightarrow b \rightarrow c = a \underbrace{\uparrow \cdots \uparrow}_{c\text{本}} b = a \uparrow^c b(a\rightarrow b=a^bとも書き換えられる)

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

: 
 (5)\qquad
 \begin{align}a \rightarrow b \rightarrow c =& \underbrace{a \uparrow^{c-1} a \uparrow^{c-1} \cdots a \uparrow^{c-1} a \uparrow^{c-1} a \uparrow^{c-1} a}_{b\text{ copies of }a} = a \uparrow^{c-1}\underbrace{a \uparrow^{c-1} a \uparrow^{c-1} \cdots a \uparrow^{c-1} a \uparrow^{c-1} a \uparrow^{c-1} a}_{b-1\text{ copies of }a}= a \uparrow^{c-1} a \uparrow^c \left(b-1\right)= a \uparrow^{c-1} \left\{a \rightarrow \left(b-1\right)\rightarrow c\right\}\\=& a \rightarrow \left\{a \rightarrow (b-1) \rightarrow c\right\} \rightarrow (c-1)
 =
\underbrace{
 a \rightarrow \biggl(a \rightarrow \biggl( \cdots \rightarrow \Bigl(
  a \rightarrow ( \quad a }_{b} \quad
\underbrace{
  ) \rightarrow (c-1)
 \Bigr) \rightarrow \cdots \biggr) \rightarrow (c-1)\biggr) \rightarrow (c-1)
}_{b-1}\end{align}


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

: 
 (6)\qquad
 X \rightarrow b \rightarrow c
 =
 X \rightarrow \left\{X \rightarrow (b-1) \rightarrow c\right\} \rightarrow (c-1)
 =
\underbrace{
 X \rightarrow \biggl( X \rightarrow \biggl( \cdots \rightarrow \Bigl(
  X \rightarrow ( \quad X }_{b} \quad
\underbrace{
  ) \rightarrow (c-1)
 \Bigr) \rightarrow \cdots \biggr) \rightarrow (c-1) \biggr) \rightarrow (c-1)
}_{b-1}


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

: (7)\qquad a_1 \rightarrow \cdots \rightarrow a_n \rightarrow 1 = a_1 \rightarrow \cdots \rightarrow a_n

また、この規則から長さが  のチェーンは累乗となる。

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

:a\rightarrow b\rightarrow\cdot\cdot\cdot \rightarrow z \rightarrow1 \rightarrow\cdot\cdot\cdot=a\rightarrow b\rightarrow\cdot\cdot\cdot \rightarrow z 
:

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

* 任意の正の整数は、長さ  のチェーンである。
* 長さ  のチェーンに、右向き矢印  と正の整数を繋げたものは、長さ  のチェーンとなる。

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

* 長さ  のチェーン（空チェーン）は、 に等しい。
* 長さ  のチェーン  は、 に等しい。
* 長さ  のチェーン  は、 に等しい。
* 長さ  のチェーン  は  に、 は  に各々等しい。
*  は  に等しい。即ちチェーン右端の  は取り除くことができる。
*  は  に等しい。即ちチェーン右端の  は取り除くことができる。
*  は X \rightarrow \left\{ X \rightarrow p \rightarrow \left(q+1\right)  \right\} \rightarrow q に等しい。

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

: \begin{align}
 X \rightarrow (p + 1) \rightarrow (q + 1)
 &=
\underbrace{
 X \rightarrow \biggl( \cdots \rightarrow \Bigl(
  X \rightarrow (
}_{p}
   \quad X \quad
\underbrace{
  ) \rightarrow q
 \Bigr) \rightarrow \cdots \biggr) \rightarrow q
}_{p}
\\
 &= \underbrace{ f( \cdots f( }_{p} \quad X \quad \underbrace{ ) \cdots ) }_{p}
\\
 &= f^p(X)
\end{align}

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

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

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

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

* a \rightarrow b=a^b
* \displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z\rightarrow1={\displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z}
* \displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z\rightarrow1\rightarrow\dots={\displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z}

* a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z=a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow (a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow (y-1)\rightarrow z)\rightarrow (z-1)

## 性質
以下、項（正の整数）を小文字  、チェーン（および部分チェーン）を大文字  で表す。

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

## 例
以下は長さが  のチェーンの計算例である。

* 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 

* 
: 
: 
: 
: 
: 
: 
: 
: 

* 
: 
: 
: 
: 
: 

以下は長さが  のチェーンのクヌースの矢印表記による展開例(縦横展開)である。
: 
 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 1
  &=&
  p \underbrace{\uparrow \cdots \uparrow}_{ r\text{本} } q
 \end{matrix}

: 
 \left.
 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 2
  =p \rightarrow q \rightarrow \left\{p \rightarrow q \rightarrow (r-1) \rightarrow 2\right\} \rightarrow 1
  =p \rightarrow q \rightarrow \left\{p \rightarrow q \rightarrow (r-1) \rightarrow 2\right\}
  =\underbrace{p \rightarrow q \rightarrow (p \rightarrow q \rightarrow \cdots (p \rightarrow q \rightarrow (}_{r}1)\underbrace{ \rightarrow 1)\cdots \rightarrow 1)}_{r}
  &=&p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow}_{\scriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow}_{\scriptstyle   \underbrace{\quad~ \vdots ~\quad}_{\scriptstyle p \underbrace{\uparrow \cdots \uparrow}_{\scriptstyle p^q\text{本} } q\text{本} }       } q\text{本} } q
 \end{matrix}
 \right \} {\scriptstyle r\text{層} }

: 
 \begin{matrix}
  p \rightarrow q \rightarrow r \rightarrow 3
  =\underbrace{p \rightarrow q \rightarrow (p \rightarrow q \rightarrow \cdots (p \rightarrow q \rightarrow (}_{r}1)\underbrace{ \rightarrow 2)\cdots \rightarrow 2)}_{r}
  &=& \\
  & & \\
  & & \\
  & & \\
  & & \\
  & & \\
  & & \\
 \end{matrix}
 \underbrace{
  \left.
   \begin{matrix}
    p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q \\
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q\text{本} }\\
    {\scriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptstyle   \underbrace{\quad~ \vdots ~\quad}_{\scriptstyle p \underbrace{\uparrow \cdots \uparrow}_{\scriptstyle p^q\text{本} } q\text{本} }       }
   \end{matrix}
  \right \}
  \left.
   \begin{matrix}
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow} q\text{層} }\\
    {\scriptscriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow} q\text{本} }\\
    {\scriptscriptstyle               \quad~ \vdots ~\quad        }\\
    {\scriptscriptstyle   \underbrace{\quad~ \vdots ~\quad}_{\scriptscriptstyle p \underbrace{\uparrow \cdots \uparrow}_{\scriptscriptstyle p^q\text{本} } q\text{本} }       }
   \end{matrix}
  \right \}
  \cdots
  \left\}
   \begin{matrix}
    {\scriptstyle p \underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow}_{\scriptscriptstyle p \underbrace{\uparrow \cdots \cdots \uparrow}_{\scriptscriptstyle   \underbrace{\quad~ \vdots ~\quad}_{\scriptscriptstyle p \underbrace{\uparrow \cdots \uparrow}_{\scriptscriptstyle p^q\text{本} } q\text{本} }       } q\text{本} } q\text{層} }
   \end{matrix}
  \right \} {\scriptscriptstyle p^q\text{層} }
 }_{r}


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

:*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* &minus; 3) + 3

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

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

コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。
: 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 
:= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27 \rightarrow 2) \rightarrow 2\, 
:= g^ {3 \rightarrow 3 \rightarrow 27 \rightarrow 2}(1) 
:= g^{g^{27}(1)}(1)  

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


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

## CG関数
コンウェイとにより共同制作されたCG関数と呼ばれる単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:

cg(n) = \underbrace{n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n}_{\text{長 さ }n}

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

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

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

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

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

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{ 本 の 矢}}（あくまで\rightarrow_{b-1}がc本、という意味）

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

#### 定義
a \rightarrow_1b=a^b

a \rightarrow_1b \rightarrow_1n=a\uparrow^nb

a \rightarrow_nb  \rightarrow_nc\dots \rightarrow_nz \rightarrow_n1=a \rightarrow_nb  \rightarrow_nc\dots \rightarrow_nz 

a \rightarrow_nb  \rightarrow_nc\dots \rightarrow_nz \rightarrow_n1 \rightarrow_n\dots=a \rightarrow_nb  \rightarrow_nc\dots \rightarrow_nz 

a \rightarrow_nb \rightarrow_n\dots\rightarrow_ny \rightarrow_nz=a \rightarrow_nb \rightarrow_n\dots\rightarrow_n(a \rightarrow_nb \rightarrow_n\dots(y-1)\rightarrow_nz)\rightarrow_n(z-1)

a\rightarrow_nb=\underbrace{a\rightarrow_{n-1}a\rightarrow_{n-1}\dots\rightarrow_{n-1}a}_{\text{長 さ}\ \ b+1}

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

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

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

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

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

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{ 本 の 矢}}

とすると、a \rightarrow_b c \rightarrow_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(グラハム数)、つまり\underbrace {G\rightarrow G\rightarrow\dots\rightarrow G}_{\text{グ ラ ハ ム 数 個 の G}}より遥かに大きい。ふぃっしゅ数バージョン1はピーター・ハーフォードの拡張チェーン表記による近似で≒5→264→22、ふぃっしゅ数バージョン2は同表記による近似で≒3→643→642程度の大きさとなる。このようにふぃっしゅ数はバージョン1とバージョン2までは、拡張チェーン系の表記の範囲で近似可能であるが、バージョン3以上になるとそのレベルをも遥かに本質的に超えてしまう。

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

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

## 出典

## 参考文献
* https://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm 
* http://home.earthlink.net/~mrob/pub/math/largenum-4.html 

## 関連項目
* 巨大数
* クヌースの矢印表記
* 配列表記