クヌースの矢印表記

クヌースの矢印表記（クヌースのやじるしひょうき、英: Knuth's up-arrow notation）とは、1976年にドナルド・クヌースが巨大数を表現するために発明した表記法である^[1][2]。これは、乗算が加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復（テトレーション）を表す演算の表記法である。例えば宇宙論で使われた最大の数は、クヌースの矢印表記で表すとおよそ${\displaystyle 10\uparrow \uparrow 5}$^{[注釈 1]}である。このように、クヌースの矢印表記は現実世界の事物で例えるにはあまりにも大きすぎるような巨大数を簡単に表現できる表記法の一つである。

クヌースの矢印表記を指す用語として、日本ではタワー表記という呼称も用いられる^[3][4]。一方英語では、テトレーションを指数で表記した時の、まるで塔のように高く積みあがる様子を指した「Power tower^[5]」という語はあるが、タワー表記に相当する用語は見受けられない。

クヌースの矢印表記のさらに拡張となる表記法には、コンウェイのチェーン表記などがある。

導入

加算→乗算→冪乗

乗算は、加算の反復によって定義できる。

${\displaystyle a\times b=\underbrace {a+a+\dots +a} _{b{\text{ copies of }}a}}$

冪乗は、乗算の反復によって定義できる。

${\displaystyle a^{b}=\underbrace {a\times a\times \dots \times a} _{b{\text{ copies of }}a}}$

なお、一部の初期のコンピュータでは、上向き矢印を冪乗演算子に使った^[6]ので、それを使うと

${\displaystyle a\uparrow b=\underbrace {a\times a\times \dots \times a} _{b\mathrm {\ copies\ of\ } a}=a^{b}}$ 。

例として、 グーゴルプレックス ${\displaystyle 10^{10^{100}}}$ は、10↑10↑100 と書ける。

テトレーション

ここでクヌースは、二重矢印をテトレーション（指数計算の反復）を表す演算子として定義した^[2]。

${\displaystyle a\uparrow \uparrow b=\underbrace {a\uparrow a\uparrow \cdots \uparrow a} _{b{\text{ copies of }}a}=\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} _{b{\text{ copies of }}a}}$

これを用いると、

${\displaystyle {\begin{aligned}2\uparrow \uparrow 2&=2^{2}=4\,\\2\uparrow \uparrow 3&=2^{2^{2}}=2^{4}=16\,\\2\uparrow \uparrow 4&=2^{2^{2^{2}}}=2^{2^{4}}=2^{16}=65536\,\\2\uparrow \uparrow 5&=2^{2^{2^{2^{2}}}}=2^{2^{16}}=2^{65536}\approx 2.003\times 10^{19728}\end{aligned}}}$

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.258\times 10^{3638334640024}}$

${\displaystyle 10\uparrow \uparrow 3=10^{10^{10}}=10^{10000000000}}$ (10の100億乗)

${\displaystyle 10\uparrow \uparrow 4=10^{10^{10^{10}}}=10^{10^{10000000000}}}$

などと書ける。

それ以上

さらにクヌースは、三重以上の矢印演算子を定義した。三重矢印は二重矢印による演算を反復する演算子であり、ペンテーションを表す。

${\displaystyle a\uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} _{b{\text{ copies of }}a}}$

同様に、四重矢印演算子も定義できる。これはヘキセーションを表す。

${\displaystyle a\uparrow \uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} _{b\mathrm {\ copies\ of\ } a}}$

これを一般的に述べると、n 重の矢印演算子は、(n -1) 重の矢印演算子の反復として表すことができる^[2]。

${\displaystyle a\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } _{n{\text{ pieces of the arrow}}}b=\underbrace {a\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } _{(n-1){\text{ pieces of the arrow}}}a\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } _{(n-1){\text{ pieces of the arrow}}}\cdots a\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } _{(n-1){\text{ pieces of the arrow}}}a} _{b{\text{ copies of }}a}}$

具体例を挙げると、14↑↑↑↑4 は 14↑↑↑14↑↑↑14↑↑↑14 である。

なお、矢印を使った指数の記法 ${\displaystyle a\uparrow b=a^{b}}$ も、クヌースの矢印記号の特殊例（一重矢印）として再解釈される。

定義

n 重の矢印演算子を ${\displaystyle \uparrow ^{n}}$ と略記することにする。このとき、クヌースの矢印表記は、次のように定義される。

${\displaystyle a\uparrow ^{n}b={\begin{cases}1,&{\mbox{if }}b=0\\a^{b},&{\mbox{if }}n=1\\a\uparrow ^{n-1}\left(a\uparrow ^{n}\left(b-1\right)\right),&{\text{otherwise }}\forall a,b\in \mathbb {Z} ,\forall n\in \mathbb {N} \end{cases}}}$

ただし、b ≥ 0である。なおa⁰ = 1なので、最初の2式の優先順位はどちらでもよい。

結合規則

クヌースの矢印（通常の指数計算である a↑b も含む）は右結合である。つまり、${\displaystyle a\uparrow b\uparrow c}$ と書かれたときこれは ${\displaystyle a\uparrow \left(b\uparrow c\right)}$ を表し、${\displaystyle \left(a\uparrow b\right)\uparrow c}$ ではない。

具体例を挙げると、

${\displaystyle 3\uparrow 2\uparrow 3}$

は

${\displaystyle 3\uparrow \left(2\uparrow 3\right)=3\uparrow 8=3^{8}=6561}$

だが、

${\displaystyle {\begin{aligned}\left(3\uparrow 2\right)\uparrow 3=&9\uparrow 3=9^{3}\\=&3\uparrow \left(2\times 3\right)=3\uparrow 6=3^{6}\\=&729\end{aligned}}}$

ではない。

他の記法との関係

既に述べた通り、1重のクヌースの矢印は冪乗を表す。また、2重のクヌースの矢印はテトレーションを表す。

${\displaystyle a\uparrow b=a^{b}}$

${\displaystyle a\uparrow \uparrow b={}^{b}a}$

また、${\displaystyle \uparrow ^{n}}$ を用いてアッカーマン関数の一般解を表すことができる。

${\displaystyle \operatorname {Ack} \left(n,b\right)=\left\{2\uparrow ^{n-2}\left(b+3\right)\right\}-3\quad {\mbox{if }}n\geq 3}$

ハイパー演算子は、積・和・後者関数も表せる以外は、${\displaystyle \uparrow ^{n}}$ を使ったクヌースの記法と等価である。

${\displaystyle \operatorname {hyper} \left(a,n,b\right)=a\uparrow ^{n-2}b\quad {\mbox{if }}n\geq 3}$

コンウェイのチェーン表記は、3連では ${\displaystyle \uparrow ^{n}}$ を使ったクヌースの矢印表記と等価だが、さらに長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数、たとえばグラハム数の範囲などを表すことができる。

${\displaystyle a\to b\to n=a\uparrow ^{n}b}$

配列表記も3変数ではクヌースの矢印表記と等価だが、この配列表記をさらに長く続けた場合は、コンウェイのチェーン表記よりもはるかに効率的に数が爆発する。具体的には、4変数の配列表記でコンウェイのチェーン表記レベル、5変数でその拡張表記レベルとなり、6変数以上となるとそのレベルを超える。

${\displaystyle \{a,b,n\}=a\uparrow ^{n}b}$

また、多角形表記も巨大数のレベルとしてはクヌースの矢印表記レベルの巨大数を作ることができ、ハイパーE表記も拡張表記でない段階ではクヌースの矢印表記と同程度の増加速度である。

フォントの都合による代替表記

コンピュータ上でのテキストとして表記する場合、フォントによっては↑のような記号が無い場合もあるため、a^^bのようにサーカムフレックスを並べる表記を行う場合がある。クヌース自身も、これを代替的あるいは簡便な記法として認めている。

指数表記 a^b のかわりに a^b と書くのも、これと同じである。