クヌースの矢印表記

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

クヌースの矢印表記(クヌースのやじるしひょうき、: Knuth's up-arrow notation)とは、1976年ドナルド・クヌース巨大数を表現するために発明した表記法である[1][2]。これは、乗算加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復(テトレーション)を表す演算の表記法である。また、クヌースの矢印表記を拡張した表記法に、コンウェイのチェーン表記配列表記があり、またさらに配列表記を拡張したBEAFがある。

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

導入[編集]

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

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

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

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

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

テトレーション[編集]

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

これを用いると、

(10の100億乗)

などと書ける。 二重矢印演算子により、非常に大きな巨大数を導くことができる[2]

それ以上[編集]

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

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

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

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

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

優先規則[編集]

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

具体例を挙げると、

だが、

ではない。

拡張記法[編集]

n重矢印演算子[編集]

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

写像の冪[編集]

は、関数

m-th functional power[訳語疑問点]

である。つまり

である。たとえば、

定義[編集]

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

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

functional power[訳語疑問点]を使って、次のようにも定義できる。

他の記法との関係[編集]

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

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

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

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

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

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

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

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

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

出典[編集]

  1. ^ フィッシュ『巨大数論 第2版』インプレス R&D、東京、2017年。ISBN 9784802093194
  2. ^ a b c d e Knuth, D. E. (1976-12-17). “Mathematics and Computer Science: Coping with Finiteness” (英語). Science 194 (4271): 1235–1242. doi:10.1126/science.194.4271.1235. ISSN 0036-8075. https://www.sciencemag.org/lookup/doi/10.1126/science.194.4271.1235. 
  3. ^ S.O. (2017年2月2日). “大きすぎて全世界のインクを使っても書けない「巨大数」の世界”. QuizKnock inc.. 2021年3月28日閲覧。
  4. ^ ギネスブックに載った世界一大きな数がヤバすぎる!”. 学生団体POMB. 2021年3月28日閲覧。
  5. ^ Galidakis, Ioannis and Weisstein, Eric W. “Power Tower”. Wolfram MathWorld. 2021年3月28日閲覧。

関連項目[編集]