コンウェイのチェーン表記
コンウェイのチェーン表記(コンウェイのチェーンひょうき、Conway chained arrow notation)とは、1995年にイギリスの数学者ジョン・ホートン・コンウェイによって導入された巨大数の表記法の一つである。
クヌースの矢印表記やアッカーマン関数などより比較的強い演算である。具体的には、3つ組ではクヌースの矢印表記と等価だが、更に長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数を表すことができる。
加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって a ↑ b  ab と表して、さらに ↑ の反復を ↑↑(テトレーション)、↑↑ の反復を ↑↑↑(ペンテーション)、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。
\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} \,\!
コンウェイのチェーン表記は、このクヌースの矢印表記の一般化、拡張である。以下チェーンの各項はすべて自然数であるものとする。
コンウェイはまず長さが 3 のチェーンを、クヌースの矢印表記を用いて次のように与えた。
(4)\qquad a \rightarrow b \rightarrow c = a \underbrace{\uparrow \cdots \uparrow}_{c\text{本} b = a \uparrow^c b(a\rightarrow b=a^bとも書き換えられる)
このチェーンによって (3) を書き換えると次のような式になる。これは末尾 → c のチェーンを末尾 → (c − 1) のチェーンに分解する式となっている。
(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}
この式の a を部分チェーン X に置き換えることで、長さが 4 以上のチェーンに対する式が得られる。
(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}
さらにコンウェイはチェーン末尾の→ 1は無視されるとした。従って式 (5), (6) を繰り返して末項を 1 にすることで、長さが 1 短いチェーンへと分解することができる。
(7)\qquad a_1 \rightarrow \cdots \rightarrow a_n \rightarrow 1 = a_1 \rightarrow \cdots \rightarrow a_n
また、この規則から長さが 2 のチェーンは累乗となる。
さらにコンウェイはチェーン途中の→ 1の右側の全ても無視されるとした。それにより4つ組チェーンの計算も行える。
a\rightarrow b\rightarrow\cdot\cdot\cdot \rightarrow z \rightarrow1 \rightarrow\cdot\cdot\cdot=a\rightarrow b\rightarrow\cdot\cdot\cdot \rightarrow z
次のようにチェーンを定義する。
任意の正の整数は、長さ 1 のチェーンである。
長さ n のチェーンに、右向き矢印 → と正の整数を繋げたものは、長さ n + 1 のチェーンとなる。
さらに p, q を正の整数、X を部分チェーンとするとき、チェーンについて以下が成り立つ。
長さ 0 のチェーン(空チェーン)は、1 に等しい。
長さ 1 のチェーン p は、p に等しい。
長さ 2 のチェーン p → q は、pq に等しい。
長さ 3 のチェーン p → q → 0 は pq に、p → 0 → 2 は 1 に各々等しい。
X → 1 は X に等しい。即ちチェーン右端の → 1 は取り除くことができる。
X → 1 → p は X に等しい。即ちチェーン右端の → 1 → p は取り除くことができる。
X → (p + 1) → (q + 1) は X \rightarrow \left\{ X \rightarrow p \rightarrow \left(q+1\right)  \right\} \rightarrow q に等しい。
ここで関数 f を f(x)  X → (x) → q とおくと、最後の二つの条件は次のようにも述べられる。但し fp は f の p 回反復合成である。
\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)
以下、項(正の整数)を小文字 a, b, ... 、チェーン(および部分チェーン)を大文字 A, B, ... で表す。
長さ 3 のチェーンは、ハイパー演算子、クヌースの矢印表記、および配列表記による表示をもつ。
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\}
任意のチェーンに対し常にただ一つの整数が定まる。
長さ n のチェーン X → p → q は適当な r によって X → r と変形できる。即ち先頭から n − 2 項を保ったまま長さを 1 短くできる。
a から始まるチェーン a → X は a の冪 at となる。
1 から始まるチェーン 1 → X は 1 に等しい。
1 より後の項はすべて無視することができる。
X \rightarrow 1 \rightarrow Y = X
先頭に 2 が連なったチェーン 2 → 2 → X は 4 に等しい。
末尾に 2 が連なったチェーン X → 2 → 2 は X → (X) に等しい。
p-q は p → (q → (-1) → 0) → (-1) に等しい。
p/q は p → (q → (-1) → 1) → 0 に等しい。
p → (q → (-1) → 2) → 1  pq → (-1) → 2 は plogq(logq(q → (+1) → 2))  plogq(logq(q))  plogq(1)  p0  1 に等しい。
以下は長さが 3 のチェーンの計算例である。
以下は長さが 4 のチェーンのクヌースの矢印表記による展開例(縦横展開)である。
\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 − 3) + 3
(n = 1 と n = 2 は A(m, −2) = −1 と A(m, −1) = 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 < G < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2 である。
証明: 定義の"反復合成を用いた規則"を適用させると、次の様になる。:
g^{64}(1)
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1))\cdots )) (64組の "3 \rightarrow 3")
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3) \rightarrow 1) \cdots ) \rightarrow 1) \rightarrow 1
= 3 \rightarrow 3 \rightarrow 64 \rightarrow 2;
\left.
\begin{matrix}
=   &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3\text{本} \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3\text{本} \\
&3\uparrow 3\text{本}
\end{matrix}
\right\} \text{64層 }
g^{64}(4) = G;
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 4))\cdots )) (64組の "3 \rightarrow 3")
\left.
\begin{matrix}
=   &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3\text{本} \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3\text{本} \\
&3\uparrow \uparrow \uparrow \uparrow 3\text{本}
\end{matrix}
\right\} \text{64層 }
g^{64}(27)
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27))\cdots )) (64組の "3 \rightarrow 3")
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3)))\cdots )) (65組の "3 \rightarrow 3")
= 3 \rightarrow 3 \rightarrow 65 \rightarrow 2 (上記のように計算する)
= g^{65}(1)
\left.
\begin{matrix}
=   &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3\text{本} \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3\text{本} \\
&3\uparrow 3\text{本}
\end{matrix}
\right\} \text{65層 }
g は単調増加なので、
g^{64}(1) < g^{64}(4) < g^{64}(27)
コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。
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 はグラハム数よりはるかに大きい。