コンウェイのチェーン表記
コンウェイとリチャード・K・ガイ(英語版)に共同制作された単純な単一引数関数は、下記の様に表記法全体にわたって対角化する様定義されていた:
c g ( n ) = n → n → n → ⋯ → n → n → n ⏟ 長 さ n {\displaystyle cg(n)=\underbrace {n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n} _{{\text{長 さ }}n}}
その出力を順に並べると:
cg(1) = 1
cg(2) = 2 → 2 = 2 = 4
cg(3) = 3 → 3 → 3 = 3↑↑↑3 = 3↑↑(3↑↑3)= 3↑↑(3↑(3↑3))= 3↑↑(3↑27)= 3↑↑7625597484987
cg(4) = 4 → 4 → 4 → 4 = 4 → 4 →(4 → 4 →(4 → 4 →(4 → 4)→ 3)→ 3)→ 3 = 4 → 4 →(4 →4 →(4 →4 → 256 →3) →3 ) →3
上記以外の書き方でされている定義もある。
書き方は違うが、意味は同じである。
以下の4つの定義でチェーン表記を定義することも可能である。
チェーン表記 a → b → c → ⋯ → y → z {\displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z} (a~zは正の整数)を以下のように定義する。
a → b = a b {\displaystyle a\rightarrow b=a^{b}}
a → b → c → ⋯ → y → z → 1 = a → b → c → ⋯ → y → z {\displaystyle \displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z\rightarrow 1={\displaystyle a\rightarrow b\rightarrow c\rightarrow \dots \rightarrow y\rightarrow z}}
a → 1 b {\displaystyle a\rightarrow _{1}b} = {\displaystyle =} a b {\displaystyle a^{b}}
a → 1 b → 1 n {\displaystyle a\rightarrow _{1}b\rightarrow _{1}n} = {\displaystyle =} a ↑ n b {\displaystyle a\uparrow ^{n}b}
a → n b → n c ⋯ → n z → n 1 {\displaystyle a\rightarrow _{n}b\rightarrow _{n}c\dots \rightarrow _{n}z\rightarrow _{n}1} = {\displaystyle =} a → n b → n c ⋯ → n z {\displaystyle a\rightarrow _{n}b\rightarrow _{n}c\dots \rightarrow _{n}z}
a → n b → n c ⋯ → n z → n 1 → n ...
{\displaystyle a\rightarrow _{n}b\rightarrow _{n}c\dots \rightarrow _{n}z\rightarrow _{n}1\rightarrow _{n}\dots } = {\displaystyle =} a → n b → n c ⋯ → n z {\displaystyle a\rightarrow _{n}b\rightarrow _{n}c\dots \rightarrow _{n}z}
a → n b → n ⋯ → n y → n z {\displaystyle a\rightarrow _{n}b\rightarrow _{n}\dots \rightarrow _{n}y\rightarrow _{n}z} = {\displaystyle =} a → n b → n ⋯ → n ( a → n b → n ... ( y − 1 ) → n z ) → n ( z − 1 ) {\displaystyle a\rightarrow _{n}b\rightarrow _{n}\dots \rightarrow _{n}(a\rightarrow _{n}b\rightarrow _{n}\dots (y-1)\rightarrow _{n}z)\rightarrow _{n}(z-1)}
a → n b = a → n − 1 a → n − 1 ⋯ → n − 1 a ⏟ 長 さ b + 1 {\displaystyle a\rightarrow _{n}b=\underbrace {a\rightarrow _{n-1}a\rightarrow _{n-1}\dots \rightarrow _{n-1}a} _{{\text{長 さ}}\ \ b+1}}
cg(5) = 5 → 5 → 5 → 5 → 5 = 5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5)→ 4)→ 4)→ 4)→ 4 = 5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 5 → 5 →(5 → 2 → 6)→ 4)→ 4)→ 4)→ 4
cg(6) = 6 → 6 → 6 → 6 → 6 → 6 = 6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6 →(6 → 6 → 6 → 6) → 5) → 5) → 5) → 5) → 5
...............
この関数は予測されるように、とても急速に増大する。
この関数は急増加関数で c g ( x ) ≈ f ω 2 ( x ) {\displaystyle cg(x)\approx f_{\omega ^{2}}(x)} と近似できる。
このチェーン表記にも、次のような拡張表記が考案されている。