他の記法との関係
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/09 09:27 UTC 版)
「クヌースの矢印表記」の記事における「他の記法との関係」の解説
既に述べた通り、1重のクヌースの矢印は冪乗を表す。また、2重のクヌースの矢印はテトレーションを表す。 a ↑ b = a b {\displaystyle a\uparrow b=a^{b}} a ↑↑ b = b a {\displaystyle a\uparrow \uparrow b={}^{b}a} また、 ↑ n {\displaystyle \uparrow ^{n}} を用いてアッカーマン関数の一般解を表すことができる。 Ack ( n , b ) = { 2 ↑ n − 2 ( b + 3 ) } − 3 if n ≥ 3 {\displaystyle \operatorname {Ack} \left(n,b\right)=\left\{2\uparrow ^{n-2}\left(b+3\right)\right\}-3\quad {\mbox{if }}n\geq 3} ハイパー演算子は、積・和・後者関数も表せる以外は、 ↑ n {\displaystyle \uparrow ^{n}} を使ったクヌースの記法と等価である。 hyper ( a , n , b ) = a ↑ n − 2 b if n ≥ 3 {\displaystyle \operatorname {hyper} \left(a,n,b\right)=a\uparrow ^{n-2}b\quad {\mbox{if }}n\geq 3} コンウェイのチェーン表記は、3連では ↑ n {\displaystyle \uparrow ^{n}} を使ったクヌースの矢印表記と等価だが、さらに長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数、たとえばグラハム数の範囲などを表すことができる。 a → b → n = a ↑ n b {\displaystyle a\to b\to n=a\uparrow ^{n}b} 配列表記も3変数ではクヌースの矢印表記と等価だが、この配列表記をさらに長く続けた場合は、コンウェイのチェーン表記よりもはるかに効率的に数が爆発する。具体的には、4変数の配列表記でコンウェイのチェーン表記レベル、5変数でその拡張表記レベルとなり、6変数以上となるとそのレベルを超える。 { a , b , n } = a ↑ n b {\displaystyle \{a,b,n\}=a\uparrow ^{n}b} また、多角形表記も巨大数のレベルとしてはクヌースの矢印表記レベルの巨大数を作ることができ、ハイパーE表記も拡張表記でない段階ではクヌースの矢印表記と同程度の増加速度である。
※この「他の記法との関係」の解説は、「クヌースの矢印表記」の解説の一部です。
「他の記法との関係」を含む「クヌースの矢印表記」の記事については、「クヌースの矢印表記」の概要を参照ください。
- 他の記法との関係のページへのリンク