クヌースの矢印表記のソースを表示

{{Expand English|Knuth's up-arrow notation|date=2024年5月}}
'''クヌースの矢印表記'''（クヌースのやじるしひょうき、{{lang-en-short|Knuth's up-arrow notation}}）とは、[[1976年]]に[[ドナルド・クヌース]]が[[巨大数]]を表現するために発明した表記法である<ref>{{Cite book |和書 |author=フィッシュ |year=2017 |title=巨大数論 第2版 |publisher=インプレス R&D |location=東京 | url=http://gyafun.jp/ln/ |isbn=9784802093194}}</ref><ref name="Knuth 1976">{{Cite journal|last=Knuth|first=D. E.|date=1976-12-17|title=Mathematics and Computer Science: Coping with Finiteness|url=https://www.sciencemag.org/lookup/doi/10.1126/science.194.4271.1235|journal=Science|volume=194|issue=4271|pages=1235–1242|language=en|doi=10.1126/science.194.4271.1235|issn=0036-8075}}</ref>。これは、[[乗算]]が[[加算]]の反復であり、[[冪乗]]が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復（[[テトレーション]]）を表す演算の表記法である。例えば[[宇宙論]]で使われた最大の数は、クヌースの矢印表記で表すとおよそ<math>10\uparrow\uparrow 5</math><ref group="注釈">複数の宇宙の全質量を1個の[[ブラックホール]]に圧縮しそれが蒸発した後に、[[ポアンカレの回帰定理]]に従い再びブラックホールができる時間。値を冪指数で表現すると<math>{10}^{{10}^{{10}^{{10}^{{10}^{1.1}}}}}\approx{10}^{{10}^{{10}^{3883775501690}}}</math>であり、桁数が非常に大きいため、時間の単位を[[プランク時間]]・[[秒]]・[[年]]のいずれにしても無視できる範囲で近似する。</ref>である。このように、クヌースの矢印表記は現実世界の事物で例えるにはあまりにも大きすぎるような巨大数を簡単に表現できる表記法の一つである。

クヌースの矢印表記を指す用語として、日本では'''タワー表記'''という呼称も用いられる<ref>{{Cite web|和書|url=https://quizknock.com/large-number|title=大きすぎて全世界のインクを使っても書けない「巨大数」の世界|accessdate=2021-03-28|publisher=QuizKnock inc.|author=S.O.|date=2017-02-02}}</ref><ref>{{Cite web|和書|url=https://enjoymath.pomb.org/?p=1453|title=ギネスブックに載った世界一大きな数がヤバすぎる！|accessdate=2021-03-28|publisher=学生団体POMB}}</ref>。一方英語では、テトレーションを[[指数関数|指数]]で表記した時の、まるで塔のように高く積みあがる様子を指した「Power tower<ref>{{Cite web|url=https://mathworld.wolfram.com/PowerTower.html|title=Power Tower|accessdate=2021-03-28|author=Galidakis, Ioannis and Weisstein, Eric W|website=Wolfram MathWorld}}</ref>」という語はあるが、タワー表記に相当する用語は見受けられない。

クヌースの矢印表記のさらに拡張となる表記法には、[[コンウェイのチェーン表記]]などがある。
==導入==
===加算→乗算→冪乗===
乗算は、加算の反復によって定義できる。
:<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>
なお、一部の初期の[[コンピュータ]]では、上向き矢印を冪乗[[演算 (数学)|演算子]]に使った<ref>[http://www.softwarepreservation.org/projects/ALGOL/book/Randell_ALGOL_60_Implementation_1964.pdf  B. Randell and L.J. Russell, ''ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer''. Academic Press, 1964]. The design of the '''Whetstone Compiler''', p.23 pp.25-26 p.49 '''p.52''' p.61 pp.152-155 p.159 p.171 pp.273-274 '''p.280''' p.287 '''pp.304-305''' p.328 p.347</ref>ので、それを使うと
:<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 と書ける。

===テトレーション===
ここでクヌースは、二重矢印を[[テトレーション]]（指数計算の反復）を表す演算子として定義した<ref name="Knuth 1976" />。
:<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} 2\uparrow\uparrow2&=2^2=4\,\\
2\uparrow\uparrow3&=2^{2^2}=2^{4}=16\,\\
2\uparrow\uparrow4&=2^{2^{2^2}}=2^{2^{4}}=2^{16}=65536\,\\
2\uparrow\uparrow5&=2^{2^{2^{2^2}}}=2^{2^{16}}=2^{{65536}}\approx 2.003\times 10^{19728} \end{align} </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^{3^{27}}=3^{7625597484987} \approx 1.258\times 10^{3638334640024}</math>
:<math>10\uparrow\uparrow3 = 10^{10^{10}} = 10^{10000000000}</math> (10の100億乗)
:<math>10\uparrow\uparrow4 = 10^{10^{10^{10}}} = 10^{10^{10000000000}}</math>
などと書ける。

===それ以上===
さらにクヌースは、三重以上の矢印演算子を定義した。三重矢印は二重矢印による演算を反復する演算子であり、[[ペンテーション]]を表す。
:<math>a\uparrow\uparrow\uparrow b= \underbrace{a \uparrow\uparrow a\uparrow\uparrow \cdots \uparrow\uparrow a}_ {b\text{ copies of }a } </math>

同様に、四重矢印演算子も定義できる。これは[[ヘキセーション]]を表す。
:<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>

これを一般的に述べると、{{Mvar|n}} 重の矢印演算子は、{{Math|(''n'' -1)}} 重の矢印演算子の反復として表すことができる<ref name="Knuth 1976" />。
:<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} }
    \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&uarr;&uarr;&uarr;&uarr;4 は 14&uarr;&uarr;&uarr;14&uarr;&uarr;&uarr;14&uarr;&uarr;&uarr;14 である。

なお、矢印を使った指数の記法 <math>a \uparrow b = a ^ b</math> も、クヌースの矢印記号の特殊例（一重矢印）として再解釈される。

== 定義 ==
{{Mvar|n}} 重の矢印演算子を <math>\uparrow^n </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), &\text{otherwise }\forall a, b\in\Z, \forall n\in\N
   \end{cases}
 </math>
ただし、{{math|{{mvar|b}}&nbsp;&ge;&nbsp;0}}である。なお{{math|{{mvar|a}}<sup>0</sup> {{=}} 1}}なので、最初の2式の優先順位はどちらでもよい。

===結合規則===
クヌースの矢印（通常の指数計算である {{math|{{mvar|a}}&#8593;{{mvar|b}}}} も含む）は右結合である。つまり、<math>a\uparrow b\uparrow c </math> と書かれたときこれは <math>a\uparrow \left(b\uparrow c\right)</math> を表し、<math>\left(a\uparrow b\right)\uparrow c</math> ではない。

具体例を挙げると、
:<math>3 \uparrow 2 \uparrow 3</math>
は
:<math>3 \uparrow \left( 2 \uparrow 3\right) = 3 \uparrow 8 =3^{8}=6561</math>
だが、
:<math>\begin{align}\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{align}</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>

[[配列表記]]も3変数ではクヌースの矢印表記と等価だが、この配列表記をさらに長く続けた場合は、コンウェイのチェーン表記よりもはるかに効率的に数が爆発する。具体的には、4変数の配列表記でコンウェイのチェーン表記レベル、5変数で[[コンウェイのチェーン表記#拡張チェーン系の表記|その拡張表記]]レベルとなり、6変数以上となるとそのレベルを超える。
:<math> \{a,b,n\} = a \uparrow^n b </math>

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{reflist}}

== 関連項目 ==
* [[巨大数]]
* [[アッカーマン関数]]
* [[多角形表記]]
* [[コンウェイのチェーン表記]]
* [[配列表記]]

{{巨大数}}

{{DEFAULTSORT:くぬうすのやしるしひようき}}
[[Category:巨大数]]
[[Category:数学の表記法]]
[[Category:数学に関する記事]]
[[Category:ドナルド・クヌース]]
[[Category:数学のエポニム]]