クヌースの矢印表記

出典: フリー百科事典『ウィキペディア（Wikipedia）』

クヌースの矢印表記またはタワー表記とは、1976年にドナルド・クヌースが巨大数を表現するために発明した表記法である。これは、乗算が加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復（テトレーション、超指数）を表す演算の表記法である。

[編集] 導入

[編集] 加算→乗算→冪乗

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

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

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

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

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

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

例として、グーゴルプレックス（10^10¹⁰⁰）は　10↑10↑100　である。

[編集] テトレーション

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

$a\uparrow\uparrow b= \underbrace{a \uparrow a \uparrow \dots \uparrow a}_ {b\mathrm{ \ copies \ of \ }a } = \underbrace{a_{}^{a^{{}^{.\,^{.\,^{.\,^a}}}}}}_ {b\mathrm{ \ copies \ of \ }a }$

この定義によると、

$3\uparrow\uparrow2=3^3=27\,\!$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\!$

$3\uparrow\uparrow5=3^{3^{3^{3^3}}}\,\!$

etc.

これにより、非常な巨大数を導くことができる。

[編集] それ以上

だがクヌースはこれに飽き足らず、「2重矢印」による演算を反復する演算子として、「3重矢印」を定義した。

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

同様に、「4重矢印」演算子も定義できる。

$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) 重の矢印演算子の反復として表すことができる。

$a \underbrace{\uparrow\uparrow\cdots\uparrow}_n b = \underbrace{a \underbrace{\uparrow\cdots\uparrow}_{n-1} a \underbrace{\uparrow\cdots\uparrow}_{n-1} a \dots a \underbrace{\uparrow\cdots\uparrow}_{n-1} a}_ {b\mathrm{ \ copies \ of \ }a }$

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

[編集] 優先規則

全てのクヌースの矢印（通常の指数計算である a↑b も含む）は、右から計算される。例えば、a↑b↑c = a↑(b↑c) であり、(a↑b)↑c ではない。

具体例を挙げると、 $3\uparrow\uparrow 3= 3 \uparrow 3 \uparrow 3 = 3^{3^3}$ は $3 \uparrow ( 3 \uparrow 3) = 3^{\left(3^3\right)}=3^{27}=7625597484987$ であり、 $(3 \uparrow 3) \uparrow 3 = \left(3^3\right)^3=27^3=19683$ ではない。