クヌースの矢印表記

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

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

導入

加算→乗算→冪乗

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

<math>a\times b=\underbrace{a+a+\dots+a}_{b\mathrm{ \ copies \ of \ }a } </math>

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

<math>a ^ b=\underbrace{a\times a\times\dots\times a} _ {b\mathrm{ \ copies \ of \ }a } </math>

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

<math>a \uparrow b=\underbrace{a\times a\times\dots\times a} _ {b\mathrm{ \ copies \ of \ }a } </math> 。

例として、グーゴルプレックス ( <math>10^{10^{100}}</math> ) は　10↑10↑100　である。

テトレーション

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

<math>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 } </math>

この定義によると、

<math>3\uparrow\uparrow2=3^3=27\,\!</math>
<math>3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!</math>
<math>3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\!</math>
<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\,\!</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 \dots \uparrow\uparrow a}_ {b\mathrm{ \ 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\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 } </math>

なお、矢印を使った指数の記法 <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^{\left(3^3\right)}=3^{27}=7625597484987</math> であり、<math>(3 \uparrow 3) \uparrow 3 = \left(3^3\right)^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\uparrow\uparrow\uparrow\uparrow\uparrow b=a\uparrow^{10} b</math> 。

functional power

<math>(a \uparrow^n)^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>(a\uparrow^n)^m b= \underbrace{a \uparrow^n a \uparrow^n \dots \uparrow^n a}_m \uparrow^n b
</math>。

たとえば、

<math>(a \uparrow) ^ 3 b = a \uparrow a \uparrow a \uparrow b = 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}(a\uparrow^n(b-1)), &\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\\
   (a\uparrow^{n-1})^b 1, &\mbox{otherwise}
  \end{cases}
</math>

他の記法との関係

すでに述べたとおり、1重のクヌースの矢印は冪乗を表す。また、2重のクヌースの矢印は左上付き数字と同じテトレーションを表す。

<math> a^b = a\uparrow b </math>
<math> {}^b a = a\uparrow\uparrow b </math>

アッカーマン関数は、<math>\uparrow^n</math> を使ったクヌースの記法でほぼ表せる。

<math> \operatorname {Ack} (n, b) = 2 \uparrow^{n-2} (b+3) - 3 \quad \mbox{if }n\ge 3 </math>

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

<math> \operatorname {hyper} (a, n, b) = 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 と書くのも、これと同じである。

「http://wikippe.e-do-match.com/index.php?title=クヌースの矢印表記&oldid=102965」から取得