アッカーマン関数の値の表
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/10 01:20 UTC 版)
「アッカーマン関数」の記事における「アッカーマン関数の値の表」の解説
アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を1から順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 (n = 1) の数値を取る。 A(m,n) の値m\n01234n01 2 3 4 5 n+1 1A(0, 1) A(0, A(1, 0)) A(0, A(1, 1)) A(0, A(1, 2)) A(0, A(1, 3)) A(0, A(1, n-1)) 2A(1, 1) A(1, A(2, 0)) A(1, A(2, 1)) A(1, A(2, 2)) A(1, A(2, 3)) A(1, A(2, n-1)) 3A(2, 1) A(2, A(3, 0)) A(2, A(3, 1)) A(2, A(3, 2)) A(2, A(3, 3)) A(2, A(3, n-1)) ︙︙ ︙ ︙ ︙ ︙ ︙ 計算できる範囲で具体的な数値に置き換えていくと、表は次のようになる。 A(m,n) の値m\n01234n01 2 3 4 5 n + 1 12 3 4 5 6 n + 2 = 2 + (n + 3) - 3 23 5 7 9 11 2 n + 3 = 2 × ( n + 3 ) − 3 {\displaystyle 2n+3=2\times (n+3)-3} 35 13 29 61 125 2 n + 3 − 3 {\displaystyle 2^{n+3}-3} 413 65533 2 65536 − 3 {\displaystyle 2^{65536}-3} 2 2 65536 − 3 {\displaystyle {2^{2^{65536}}}-3} 2 2 2 65536 − 3 {\displaystyle 2^{2^{2^{65536}}}-3} 2 2 ⋅ ⋅ ⋅ 2 ⏟ − 3 n + 3 twos {\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\text{ + 3 twos}}\end{matrix}}} 565533 2 2 ⋅ ⋅ ⋅ 2 ⏟ − 3 65536 twos {\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\65536{\text{ twos}}\end{matrix}}} A ( 4 , A ( 5 , 1 ) ) {\displaystyle A(4,A(5,1))} A ( 4 , A ( 5 , 2 ) ) {\displaystyle A(4,A(5,2))} A ( 4 , A ( 5 , 3 ) ) {\displaystyle A(4,A(5,3))} A ( 4 , A ( 5 , n − 1 ) ) {\displaystyle A(4,A(5,n-1))} 一般の値は非常に大きいが、クヌースの矢印表記、コンウェイのチェーン表記、ハイパー演算子等を使えば A ( m , n ) {\displaystyle A(m,n)} = ( 2 ↑ m − 2 ( n + 3 ) ) − 3 {\displaystyle =\left(2\uparrow ^{m-2}\left(n+3\right)\right)-3} = ( 2 → ( n + 3 ) → ( m − 2 ) ) − 3 {\displaystyle =\left(2\rightarrow \left(n+3\right)\rightarrow \left(m-2\right)\right)-3} = hyper ( 2 , m , n + 3 ) − 3 {\displaystyle =\operatorname {hyper} (2,m,n+3)-3} = h y p e r m ( 2 , n + 3 ) − 3 {\displaystyle =\operatorname {hyper{\mathit {m}}} (2,n+3)-3} と簡潔に表す事が出来る。 十分にxの値を大きくしたとき、アッカーマン関数の値は急増加関数で A ( x , a ) ≈ f ω ( x ) {\displaystyle A(x,a)\thickapprox f_{\omega }(x)} ( a {\displaystyle a} は定数)と近似できる。
※この「アッカーマン関数の値の表」の解説は、「アッカーマン関数」の解説の一部です。
「アッカーマン関数の値の表」を含む「アッカーマン関数」の記事については、「アッカーマン関数」の概要を参照ください。
- アッカーマン関数の値の表のページへのリンク