クヌースの矢印やじるし表記ひょうき

クヌースの矢印やじるし表記ひょうき（クヌースのやじるしひょうき、英えい: Knuth's up-arrow notation）とは、1976年ねんにドナルド・クヌースが巨きょ大数たいすうを表現ひょうげんするために発明はつめいした表記ひょうき法ほうである。これは、乗算じょうざんが加算かさんの反復はんぷくであり、冪べき乗じょうが乗算じょうざんの反復はんぷくであるのと同様どうようの考かんがえ方かたに基もとづくもので、冪べき乗じょうの反復はんぷく（テトレーション）を表あらわす演算えんざんの表記ひょうき法ほうである。例たとえば宇宙うちゅう論ろんで使つかわれた最大さいだいの数かずは、クヌースの矢印やじるし表記ひょうきで表あらわすとおよそ$10\uparrow \uparrow 5$である。このように、クヌースの矢印やじるし表記ひょうきは現実げんじつ世界せかいの事物じぶつで例たとえるにはあまりにも大おおきすぎるような巨きょ大数たいすうを簡単かんたんに表現ひょうげんできる表記ひょうき法ほうの一ひとつである。

クヌースの矢印やじるし表記ひょうきを指さす用語ようごとして、日本にっぽんではタワー表記ひょうきという呼称こしょうも用もちいられる。一方いっぽう英語えいごでは、テトレーションを指数しすうで表記ひょうきした時ときの、まるで塔とうのように高たかく積つみあがる様子ようすを指さした「Power tower」という語かたりはあるが、タワー表記ひょうきに相当そうとうする用語ようごは見受みうけられない。

クヌースの矢印やじるし表記ひょうきのさらに拡張かくちょうとなる表記ひょうき法ほうには、コンウェイのチェーン表記ひょうきなどがある。

導入どうにゅう

加算かさん→乗算じょうざん→冪べき乗じょう

乗算じょうざんは、加算かさんの反復はんぷくによって定義ていぎできる。

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

冪べき乗じょうは、乗算じょうざんの反復はんぷくによって定義ていぎできる。

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

なお、一部いちぶの初期しょきのコンピュータでは、上向うわむき矢印やじるしを冪べき乗じょう演算えんざん子こに使つかったので、それを使つかうと

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

例れいとして、グーゴルプレックス $10^{10^{100}}$ は、10↑10↑100 と書かける。

テトレーション

ここでクヌースは、二に重じゅう矢印やじるしをテトレーション（指数しすう計算けいさんの反復はんぷく）を表あらわす演算えんざん子ことして定義ていぎした。

$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}$

これを用もちいると、

${\begin{aligned}2\uparrow \uparrow 2&=2^{2}=4\,\\2\uparrow \uparrow 3&=2^{2^{2}}=2^{4}=16\,\\2\uparrow \uparrow 4&=2^{2^{2^{2}}}=2^{2^{4}}=2^{16}=65536\,\\2\uparrow \uparrow 5&=2^{2^{2^{2^{2}}}}=2^{2^{16}}=2^{65536}\approx 2.003\times 10^{19728}\end{aligned}}$

$3\uparrow \uparrow 2=3^{3}=27$

$3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987$

$3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.258\times 10^{3638334640024}$

$10\uparrow \uparrow 3=10^{10^{10}}=10^{10000000000}$ (10の100億おく乗じょう)

$10\uparrow \uparrow 4=10^{10^{10^{10}}}=10^{10^{10000000000}}$

などと書かける。

それ以上いじょう

さらにクヌースは、三重みえ以上いじょうの矢印やじるし演算えんざん子こを定義ていぎした。三重みえ矢印やじるしは二に重じゅう矢印やじるしによる演算えんざんを反復はんぷくする演算えんざん子こであり、ペンテーションを表あらわす。

$a\uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} _{b{\text{ copies of }}a}$

同様どうように、四よん重じゅう矢印やじるし演算えんざん子こも定義ていぎできる。これはヘキセーションを表あらわす。

$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 \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}}}\cdots a\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } _{(n-1){\text{ pieces of the arrow}}}a} _{b{\text{ copies of }}a}$

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

なお、矢印やじるしを使つかった指数しすうの記法きほう $a\uparrow b=a^{b}$ も、クヌースの矢印やじるし記号きごうの特殊とくしゅ例れい（一いち重じゅう矢印やじるし）として再さい解釈かいしゃくされる。

定義ていぎ

n 重じゅうの矢印やじるし演算えんざん子こを $\uparrow ^{n}$ と略記りゃっきすることにする。このとき、クヌースの矢印やじるし表記ひょうきは、次つぎのように定義ていぎされる。

$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),&{\text{otherwise }}\forall a,b\in \mathbb {Z} ,\forall n\in \mathbb {N} \end{cases}}$

ただし、b ≥ 0である。なおa⁰ = 1なので、最初さいしょの2式しきの優先ゆうせん順位じゅんいはどちらでもよい。

結合けつごう規則きそく

クヌースの矢印やじるし（通常つうじょうの指数しすう計算けいさんである a↑b も含ふくむ）は右みぎ結合けつごうである。つまり、$a\uparrow b\uparrow c$ と書かかれたときこれは $a\uparrow \left(b\uparrow c\right)$ を表あらわし、$\left(a\uparrow b\right)\uparrow c$ ではない。

具体ぐたい例れいを挙あげると、

$3\uparrow 2\uparrow 3$

は

$3\uparrow \left(2\uparrow 3\right)=3\uparrow 8=3^{8}=6561$

だが、

${\begin{aligned}\left(3\uparrow 2\right)\uparrow 3=&9\uparrow 3=9^{3}\\=&3\uparrow \left(2\times 3\right)=3\uparrow 6=3^{6}\\=&729\end{aligned}}$

ではない。

他たの記法きほうとの関係かんけい

既すでに述のべた通とおり、1重じゅうのクヌースの矢印やじるしは冪べき乗じょうを表あらわす。また、2重じゅうのクヌースの矢印やじるしはテトレーションを表あらわす。

$a\uparrow b=a^{b}$

$a\uparrow \uparrow b={}^{b}a$

また、$\uparrow ^{n}$ を用もちいてアッカーマン関数かんすうの一般いっぱん解かいを表あらわすことができる。

$\operatorname {Ack} \left(n,b\right)=\left\{2\uparrow ^{n-2}\left(b+3\right)\right\}-3\quad {\mbox{if }}n\geq 3$

ハイパー演算えんざん子こは、積せき・和わ・後者こうしゃ関数かんすうも表あらわせる以外いがいは、$\uparrow ^{n}$ を使つかったクヌースの記法きほうと等価とうかである。

$\operatorname {hyper} \left(a,n,b\right)=a\uparrow ^{n-2}b\quad {\mbox{if }}n\geq 3$

コンウェイのチェーン表記ひょうきは、3連れんでは $\uparrow ^{n}$ を使つかったクヌースの矢印やじるし表記ひょうきと等価とうかだが、さらに長ながく続つづけることで、クヌースの矢印やじるし表記ひょうきでは簡潔かんけつに表あらわせない、あるいは現実げんじつ的てきに表あらわせない大おおきな数かず、たとえばグラハム数すうの範囲はんいなどを表あらわすことができる。

$a\to b\to n=a\uparrow ^{n}b$

配列はいれつ表記ひょうきも3変数へんすうではクヌースの矢印やじるし表記ひょうきと等価とうかだが、この配列はいれつ表記ひょうきをさらに長ながく続つづけた場合ばあいは、コンウェイのチェーン表記ひょうきよりもはるかに効率こうりつ的てきに数かずが爆発ばくはつする。具体ぐたい的てきには、4変数へんすうの配列はいれつ表記ひょうきでコンウェイのチェーン表記ひょうきレベル、5変数へんすうでその拡張かくちょう表記ひょうきレベルとなり、6変数へんすう以上いじょうとなるとそのレベルを超こえる。

$\{a,b,n\}=a\uparrow ^{n}b$

また、多角たかく形がた表記ひょうきも巨きょ大数たいすうのレベルとしてはクヌースの矢印やじるし表記ひょうきレベルの巨きょ大数たいすうを作つくることができ、ハイパーE表記ひょうきも拡張かくちょう表記ひょうきでない段階だんかいではクヌースの矢印やじるし表記ひょうきと同どう程度ていどの増加ぞうか速度そくどである。

フォントの都合つごうによる代替だいたい表記ひょうき

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

指数しすう表記ひょうき a^b のかわりに a^b と書かくのも、これと同おなじである。

関連かんれん項目こうもく

• 巨きょ大数たいすう
• アッカーマン関数かんすう
• 多角たかく形がた表記ひょうき
• コンウェイのチェーン表記ひょうき
• 配列はいれつ表記ひょうき