クヌースの矢印表記のソースを表示
←
クヌースの矢印表記
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''クヌースの矢印表記'''または'''タワー表記'''とは、[[1976年]]に[[ドナルド・クヌース]]が[[巨大数]]を表現するために発明した表記法である。これは、[[乗算]]が[[加算]]の反復であり、[[冪乗]]が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復([[テトレーション]]、超指数)を表す演算の表記法である。 ==導入== ===加算→乗算→冪乗=== 乗算は、加算の反復によって定義できる。 :<math>a\times b=\underbrace{a+a+\dots+a}_{b\mathrm{ \ copies \ of \ }a } </math> 冪乗は、乗算の反復によって定義できる。 :<math>a ^ b=\underbrace{a\times a\times\dots\times a} _ {b\mathrm{ \ copies \ of \ }a } </math> なお、一部の初期の[[コンピュータ]]では、上向き矢印を冪乗[[演算子]]に使ったので、それを使うと :<math>a \uparrow b=\underbrace{a\times a\times\dots\times a} _ {b\mathrm{ \ copies \ of \ }a } </math> 。 例として、[[グーゴルプレックス]] ( <math>10^{10^{100}}</math> ) は 10↑10↑100 である。 ===テトレーション=== ここでクヌースは、二重矢印をテトレーション(指数計算の反復)を表す演算子として定義した。 :<math>a\uparrow\uparrow b= \underbrace{a \uparrow a \uparrow \dots \uparrow a}_ {b\mathrm{ \ copies \ of \ }a } = \underbrace{a_{}^{a^{{}^{.\,^{.\,^{.\,^a}}}}}}_ {b\mathrm{ \ copies \ of \ }a } </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^{7625597484987}\,\!</math> :<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\,\!</math> :etc. これにより、非常な[[巨大数]]を導くことができる。 他にも<br> :<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 \dots \uparrow\uparrow a}_ {b\mathrm{ \ 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\uparrow}_n b = \underbrace{a \underbrace{\uparrow\cdots\uparrow}_{n-1} a \underbrace{\uparrow\cdots\uparrow}_{n-1} a \dots a \underbrace{\uparrow\cdots\uparrow}_{n-1} a}_ {b\mathrm{ \ copies \ of \ }a } </math> なお、矢印を使った指数の記法 <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^{\left(3^3\right)}=3^{27}=7625597484987</math> であり、<math>(3 \uparrow 3) \uparrow 3 = \left(3^3\right)^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\uparrow\uparrow\uparrow\uparrow\uparrow b=a\uparrow^{10} b</math> 。 ===functional power=== <math>(a \uparrow^n)^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>(a\uparrow^n)^m b= \underbrace{a \uparrow^n a \uparrow^n \dots \uparrow^n a}_m \uparrow^n b </math>。 たとえば、 :<math>(a \uparrow) ^ 3 b = a \uparrow a \uparrow a \uparrow b = 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}(a\uparrow^n(b-1)), &\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\\ (a\uparrow^{n-1})^b 1, &\mbox{otherwise} \end{cases} </math> ==他の記法との関係== すでに述べたとおり、1重のクヌースの矢印は冪乗を表す。また、2重のクヌースの矢印は左上付き数字と同じテトレーションを表す。 :<math> a^b = a\uparrow b </math> :<math> {}^b a = a\uparrow\uparrow b </math> [[アッカーマン関数]]は、<math>\uparrow^n</math> を使ったクヌースの記法でほぼ表せる。 :<math> \operatorname {Ack} (n, b) = 2 \uparrow^{n-2} (b+3) - 3 \quad \mbox{if }n\ge 3 </math> [[ハイパー演算子]]は、積・和・[[後者関数]]も表せる以外は、<math>\uparrow^n</math> を使ったクヌースの記法と等価である。 :<math> \operatorname {hyper} (a, n, b) = 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 と書くのも、これと同じである。 [[Category:数学の表記法|くぬうすのやしるしひようき]] [[Category:数学に関する記事|くぬうすのやしるしひようき]]
クヌースの矢印表記
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報