クヌースの矢印表記
クヌースの矢印表記とは、1976年にドナルド・クヌースが巨大数を表現するために発明した表記法である[1]。これは、乗算が加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復(テトレーション、超指数)を表す演算の表記法である。また、クヌースの矢印表記を拡張した表記法に、コンウェイのチェーン表記やBEAFがある。
Contents
導入
加算→乗算→冪乗
乗算は、加算の反復によって定義できる。
- [math]a\times b=\underbrace{a+a+\dots+a}_{b\text{ copies of }a } [/math]
冪乗は、乗算の反復によって定義できる。
- [math]a ^ b=\underbrace{a\times a\times\dots\times a} _ {b\text{ copies of }a } [/math]
なお、一部の初期のコンピュータでは、上向き矢印を冪乗演算子に使ったので、それを使うと
- [math]a \uparrow b=\underbrace{a\times a\times\dots\times a} _ {b\mathrm{ \ copies \ of \ }a }=a ^ b [/math] 。
例として、グーゴルプレックス [math]10^{10^{100}}[/math] は、10↑10↑100 と書ける。
テトレーション
ここでクヌースは、二重矢印をテトレーション(指数計算の反復)を表す演算子として定義した。肩に乗って行く様子から,タワー表記とも呼ぶ.
- [math]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 } [/math]
この定義によると、
- [math] \begin{align} 3\uparrow\uparrow2&=3^3=27\,\\ 3\uparrow\uparrow3&=3^{3^3}=3^{27}=7625597484987\,\\ 3\uparrow\uparrow4&=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\\ &\approx 1.258\times 10^{3638334640024} \\ 3\uparrow\uparrow5&=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\\ &\approx 3^{1.258\times 10^{3638334640024}} \end{align} [/math]
- etc.
これにより、非常に大きな巨大数を導くことができる。
他にも
- [math]10\uparrow\uparrow3 = 10^{10^{10}} = 10^{10000000000}[/math] (10の100億乗)
- [math]10\uparrow\uparrow4 = 10^{10^{10^{10}}} = 10^{10^{10000000000}}[/math]
などがある。
それ以上
だがクヌースはこれに飽き足らず、「2重矢印」による演算を反復する演算子として、「3重矢印」(ペンテーションを表す)を定義した。
- [math]a\uparrow\uparrow\uparrow b= \underbrace{a \uparrow\uparrow a\uparrow\uparrow \cdots \uparrow\uparrow a}_ {b\text{ copies of }a } [/math]
同様に、「4重矢印」演算子(ヘキセーションを表す)も定義できる。
- [math]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 } [/math]
これを一般的に述べると、n 重の矢印演算子は、(n − 1) 重の矢印演算子の反復として表すことができる。
- [math]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} } a \cdots a \underbrace{\uparrow\uparrow \cdots \cdots \cdots \cdots \uparrow}_{(n-1) \text{ pieces of the arrow} } a}_ {b\text{ copies of }a } [/math]
具体例を挙げると、14↑↑↑↑4 は 14↑↑↑14↑↑↑14↑↑↑14 である。
なお、矢印を使った指数の記法 [math]a \uparrow b = a ^ b[/math] も、クヌースの矢印記号の特殊例(一重矢印)として再解釈される。
優先規則
全てのクヌースの矢印(通常の指数計算である a↑b も含む)は、右から計算される。例えば、a↑b↑c = a↑(b↑c) であり、(a↑b)↑c ではない。
具体例を挙げると、
- [math]3\uparrow\uparrow 3= 3 \uparrow 3 \uparrow 3 = 3^{3^3}[/math]
は
- [math]3 \uparrow ( 3 \uparrow 3) = 3 \uparrow 27 =3^{27}=7625597484987[/math]
であり、
- [math](3 \uparrow 3) \uparrow 3 =27 \uparrow 3=27^3=19683[/math]
ではない。
拡張記法
n重矢印演算子
n 重の矢印演算子を単に [math]\uparrow^n[/math] と書く。たとえば、
- [math]a\uparrow\uparrow b=a\uparrow^2 b,[/math]
- [math]a\uparrow\uparrow\uparrow\uparrow\uparrow b=a\uparrow^{5} b.[/math]
functional power
[math] \left(a \uparrow^n \right)^m b[/math] は、関数
- [math]f(x) = a \uparrow^n x[/math]
の m-th functional power
- [math]f^m(x) = ( \underbrace{f \circ f \circ \cdots \circ f}_m ) (x) = \underbrace{ f(f( \cdots (f }_m(x)) \cdots ))[/math]
である。つまり
- [math] \left(a\uparrow^n \right)^m b= \underbrace{a \uparrow^n a \uparrow^n \cdots \uparrow^n a \uparrow^n }_{m \text{ copies of } a \uparrow^n } b [/math]
である。たとえば、
- [math] \left(a \uparrow \right) ^ 3 b = a \uparrow a \uparrow a \uparrow b = a \uparrow \left(a \uparrow \left(a \uparrow b \right) \right) = a^{a^{a^{b}}}.[/math]
定義
クヌースの矢印表記は、次のように定義される。
- [math] 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), &\mbox{otherwise} \end{cases} [/math]
ここで、a, b, n は整数である。ただし、b ≥ 0, n ≥ 1 である。なおa0 = 1なので、最初の2式の優先順位はどちらでもよい。
functional powerを使って、次のようにも定義できる。
- [math] a\uparrow^n b= \begin{cases} 1, &\mbox{if }b=0\\ a^b, &\mbox{if }n=1\\ \left(a\uparrow^{n-1}\right)^b 1, &\mbox{otherwise} \end{cases} [/math]
他の記法との関係
すでに述べたとおり、1重のクヌースの矢印は冪乗を表す。また、2重のクヌースの矢印は左上付き数字と同じテトレーションを表す。
- [math] a\uparrow b = a^b[/math]
- [math] a\uparrow\uparrow b = {}^b a[/math]
また、[math]\uparrow^n[/math] を用いてアッカーマン関数の一般解を表すことができる。
- [math] \operatorname {Ack} \left(n, b \right) = \left\{ 2 \uparrow^{n-2} \left(b+3 \right) \right\} - 3 \quad \mbox{if }n\ge 3 [/math]
ハイパー演算子は、積・和・後者関数も表せる以外は、[math]\uparrow^n[/math] を使ったクヌースの記法と等価である。
- [math] \operatorname {hyper} \left(a, n, b \right) = a \uparrow^{n-2} b \quad \mbox{if }n\ge 3 [/math]
コンウェイのチェーン表記は、3連では [math]\uparrow^n[/math] を使ったクヌースの矢印表記と等価だが、さらに長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数、たとえばグラハム数の範囲などを表すことができる。
- [math] a \to b \to n = a \uparrow^n b [/math]
フォントの都合による代替表記
コンピュータ上でのテキストとして表記する場合、フォントによっては↑のような記号が無い場合もあるため、a^^bのようにサーカムフレックスを並べる表記を行う場合がある。クヌース自身も、これを代替的あるいは簡便な記法として認めている。
指数表記 ab のかわりに a^b と書くのも、これと同じである。