メインメニューを開く

クヌースの矢印表記とは、1976年ドナルド・クヌース巨大数を表現するために発明した表記法である[1]。これは、乗算加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復(テトレーション、超指数)を表す演算の表記法である。また、クヌースの矢印表記を拡張した表記法に、コンウェイのチェーン表記BEAFがある。

導入編集

加算→乗算→冪乗編集

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

 

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

 

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

 

例として、グーゴルプレックス   は、10↑10↑100 と書ける。

テトレーション編集

ここでクヌースは、二重矢印をテトレーション(指数計算の反復)を表す演算子として定義した。肩に乗って行く様子から,タワー表記とも呼ぶ.

 

この定義によると、

 
etc.

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

他にも

 
 
 
 
  (10の100億乗)
 

などがある。

それ以上編集

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

 

同様に、「4重矢印」演算子(ヘキセーションを表す)も定義できる。

 

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

 

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

なお、矢印を使った指数の記法   も、クヌースの矢印記号の特殊例(一重矢印)として再解釈される。

優先規則編集

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

具体例を挙げると、

 

 

であり、

 

ではない。

拡張記法編集

n重矢印演算子編集

n 重の矢印演算子を単に   と書く。たとえば、

 
 

functional power編集

  は、関数

 

m-th functional power

 

である。つまり

 

である。たとえば、

 

定義編集

クヌースの矢印表記は、次のように定義される。

 

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

functional powerを使って、次のようにも定義できる。

 

他の記法との関係編集

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

 
 

また、  を用いてアッカーマン関数の一般解を表すことができる。

 

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

 

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

 

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

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

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

出典編集

  1. ^ フィッシュ『巨大数論 第2版』インプレス R&D、東京、2017年。ISBN 9784802093194

関連項目編集