|
|
| 1行目: |
1行目: |
| − | '''クヌースの矢印表記'''とは、[[1976年]]に[[ドナルド・クヌース]]が[[巨大数]]を表現するために発明した表記法である<ref>{{Cite book |和書 |author=フィッシュ |year=2017 |title=巨大数論 第2版 |publisher=インプレス R&D |location=東京 | url=http://gyafun.jp/ln/ |isbn=9784802093194}}</ref>。これは、[[乗算]]が[[加算]]の反復であり、[[冪乗]]が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復（[[テトレーション]]、超指数）を表す演算の表記法である。また、クヌースの矢印表記を拡張した表記法に、[[コンウェイのチェーン表記]]や[[BEAF]]がある。
| + | {{テンプレート:20180815sk}} |
| − | | |
| − | ==導入==
| |
| − | ===加算→乗算→冪乗===
| |
| − | 乗算は、加算の反復によって定義できる。
| |
| − | :<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>
| |
| − | なお、一部の初期の[[コンピュータ]]では、上向き矢印を冪乗[[演算子]]に使ったので、それを使うと
| |
| − | :<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 と書ける。
| |
| − | | |
| − | ===テトレーション===
| |
| − | ここでクヌースは、二重矢印をテトレーション（指数計算の反復）を表す演算子として定義した。肩に乗って行く様子から，'''タワー表記'''とも呼ぶ．
| |
| − | :<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} 3\uparrow\uparrow2&=3^3=27\,\\
| |
| − | 3\uparrow\uparrow3&=3^{3^3}=3^{27}=7625597484987\,\\
| |
| − | 3\uparrow\uparrow4&=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\\
| |
| − | &\approx 1.258\times 10^{3638334640024} \\
| |
| − | 3\uparrow\uparrow5&=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\\
| |
| − | &\approx 3^{1.258\times 10^{3638334640024}} \end{align} </math>
| |
| − | :etc.
| |
| − | これにより、非常に大きな[[巨大数]]を導くことができる。
| |
| − | | |
| − | 他にも
| |
| − | :<math>10\uparrow\uparrow3 = 10^{10^{10}} = 10^{10000000000}</math> (10の100億乗)<br>
| |
| − | :<math>10\uparrow\uparrow4 = 10^{10^{10^{10}}} = 10^{10^{10000000000}}</math><br>
| |
| − | などがある。
| |
| − | | |
| − | ===それ以上===
| |
| − | だがクヌースはこれに飽き足らず、「2重矢印」による演算を反復する演算子として、「3重矢印」（[[ペンテーション]]を表す）を定義した。
| |
| − | :<math>a\uparrow\uparrow\uparrow b= \underbrace{a \uparrow\uparrow a\uparrow\uparrow \cdots \uparrow\uparrow a}_ {b\text{ 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 \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} }
| |
| − | a \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↑↑↑↑4 は 14↑↑↑14↑↑↑14↑↑↑14 である。
| |
| − | | |
| − | なお、矢印を使った指数の記法 <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 \uparrow 27 =3^{27}=7625597484987</math>
| |
| − | であり、
| |
| − | :<math>(3 \uparrow 3) \uparrow 3 =27 \uparrow 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 b=a\uparrow^{5} b.</math>
| |
| − | | |
| − | ===functional power===
| |
| − | <math> \left(a \uparrow^n \right)^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> \left(a\uparrow^n \right)^m b= \underbrace{a \uparrow^n a \uparrow^n \cdots \uparrow^n a \uparrow^n }_{m \text{ copies of } a \uparrow^n } b
| |
| − | </math>
| |
| − | である。たとえば、
| |
| − | :<math> \left(a \uparrow \right) ^ 3 b = a \uparrow a \uparrow a \uparrow b = a \uparrow \left(a \uparrow \left(a \uparrow b \right) \right) = 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}\left(a\uparrow^n\left(b-1\right)\right), &\mbox{otherwise}
| |
| − | \end{cases}
| |
| − | </math>
| |
| − | ここで、''a'', ''b'', ''n'' は整数である。ただし、''b'' ≥ 0, ''n'' ≥ 1 である。なお''a''<sup>0</sup> = 1なので、最初の2式の優先順位はどちらでもよい。
| |
| − | | |
| − | functional powerを使って、次のようにも定義できる。
| |
| − | :<math>
| |
| − | a\uparrow^n b=
| |
| − | \begin{cases}
| |
| − | 1, &\mbox{if }b=0\\
| |
| − | a^b, &\mbox{if }n=1\\
| |
| − | \left(a\uparrow^{n-1}\right)^b 1, &\mbox{otherwise}
| |
| − | \end{cases}
| |
| − | </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>
| |
| − | | |
| − | ==フォントの都合による代替表記==
| |
| − | [[コンピュータ]]上でのテキストとして表記する場合、[[フォント]]によっては↑のような記号が無い場合もあるため、a^^bのように[[サーカムフレックス]]を並べる表記を行う場合がある。クヌース自身も、これを代替的あるいは簡便な記法として認めている。
| |
| − | | |
| − | 指数表記 ''a''<sup>''b''</sup> のかわりに a^b と書くのも、これと同じである。
| |
| − | | |
| − | == 出典 ==
| |
| − | {{reflist}}
| |
| − | | |
| − | == 関連項目 ==
| |
| − | {{巨大数}}
| |
| − | | |
| − | {{DEFAULTSORT:くぬうすのやしるしひようき}}
| |
| − | [[Category:数学の表記法]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | [[Category:ドナルド・クヌース]]
| |
| − | [[Category:エポニム]]
| |