コンウェイのチェーン表記
この表記は拡張チェーン表記と呼ばれ、同じ拡張チェーン系の回転矢印表記と同じくらいの強さである。歴史的には、回転矢印表記が先に考案され、後にそれとは独立にこのハーフォードの拡張チェーン表記が考案されたが、現在ではチェーン表記の拡張としてはより定義や記述がすっきりしているこのハーフォード式が標準的となっている。もっとも、拡張チェーン系表記のレベルの巨大数は、巨大数論的に中途半端なポジションということもあり、そのレベルの巨大数を表す場合は拡張チェーン系表記より強力な配列表記(海外)あるいは多変数アッカーマン関数(日本)を用いるのが最も主流となっている。
この表記は急増加関数で x → x x ≈ f ω 3 ( x ) {\displaystyle x\rightarrow _{x}x\approx f_{\omega ^{3}}(x)} と近似できる。
ちなみに多変数アッカーマン関数で x → x x ≈ A ( 1 , 0 , 0 , 0 , x ) {\displaystyle x\rightarrow _{x}x\approx A(1,0,0,0,x)} 程度である。
加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって a ↑ b = a と表して、さらに ↑ の反復を ↑↑(テトレーション)、↑↑ の反復を ↑↑↑(ペンテーション)、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。
( 1 ) a × b = a + a + ⋯ + a ⏟ b copies of a = a + ⋯ a + ⏟ b − 1 a ( 2 ) a ↑ b = a × a × ⋯ × a ⏟ b copies of a = a × ⋯ a × ⏟ b − 1 a ( 3 ) a ↑ c b = a ↑ c − 1 a ↑ c − 1 ⋯ ↑ c − 1 a ⏟ b copies of a = a ↑ c − 1 ⋯ a ↑ c − 1 ⏟ b − 1 a = a ↑ c − 1 a ⋯ ↑ c − 1 a ⏟ b − 1 copies of a {\displaystyle {\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}}\,\!}
以下、項(正の整数)を小文字 a, b, ... 、チェーン(および部分チェーン)を大文字 A, B, ... で表す。
長さ 3 のチェーンは、ハイパー演算子、クヌースの矢印表記、および配列表記による表示をもつ。 p → q → r = H r + 2 ( p , q ) {\displaystyle p\rightarrow q\rightarrow r=H_{r+2}(p,\,q)} p → q → r = p ↑ r q {\displaystyle p\rightarrow q\rightarrow r=p\uparrow ^{r}q} p → q → r = { p , q , r } {\displaystyle p\rightarrow q\rightarrow r=\{p,q,r\}}
任意のチェーンに対し常にただ一つの整数が定まる。
次のようにチェーンを定義する。
任意の正の整数は、長さ 1 のチェーンである。
長さ n のチェーンに、右向き矢印 → と正の整数を繋げたものは、長さ n + 1 のチェーンとなる。
さらに p, q を正の整数、X を部分チェーンとするとき、チェーンについて以下が成り立つ。
長さ 0 のチェーン(空チェーン)は、1 に等しい。
長さ 1 のチェーン p は、p に等しい。
長さ 2 のチェーン p → q は、p に等しい。
長さ 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 → { X → p → ( q + 1 ) } → q {\displaystyle X\rightarrow \left\{X\rightarrow p\rightarrow \left(q+1\right)\right\}\rightarrow q} に等しい。
p → q → r → 3 = p → q → ( p → q → ⋯ ( p → q → ( ⏟ r 1 ) → 2 ) ⋯ → 2 ) ⏟ r = p ↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ q p ↑ ⋯ ⋯ ↑ ⏟ q 本 ⋮ ⋮ ⋮ ⏟ p ↑ ⋯ ↑ ⏟ p q 本 q 本 } p ↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ q 層 p ↑ ⋯ ⋯ ↑ ⏟ q 本 ⋮ ⋮ ⏟ p ↑ ⋯ ↑ ⏟ p q 本 q 本 } ⋯ } p ↑ ⋯ ⋯ ⋯ ⋯ ↑ ⏟ p ↑ ⋯ ⋯ ↑ ⏟ ⋮ ⏟ p ↑ ⋯ ↑ ⏟ p q 本 q 本 q 本 q 層 } p q 層 ⏟ r {\displaystyle {\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}}