多変数アッカーマン関数


多変数アッカーマン関数
基本関数	後者関数
急増加関数	\(f_{\omega^\omega}(n)\)

多変数アッカーマン関数 \(A(x_1,x_2, …, x_n)\) は、2007年にたろうが考案し^[1]、ふぃっしゅっしゅ(2013)^[2]に紹介された。2変数の時にはアッカーマン関数と同じで、3変数以上になると配列表記と同じ程度の増加率となる多重再帰関数である。

定義[]

X : 0個以上の0以上の整数
Y : 0個以上の0
a, b : 0以上の整数

\begin{eqnarray*} A(Y, a) & = & a+1 \\ A(X, b+1, 0) & = & A(X, b, 1) \\ A(X, b+1, a+1) & = & A( X, b, A(X, b+1, a) ) \\ A(X, b+1, 0, Y, a ) & = & A(X, b, a, Y, a) \end{eqnarray*}

計算[]

チェーン表記を使い、グラハム数との大きさ比較をする。2変数では通常のアッカーマン関数と同じなので

\begin{eqnarray*} A(x,y) & \approx & 3 \rightarrow y \rightarrow x-2 \\ \end{eqnarray*}

となる。3変数では

\begin{eqnarray*} A(1,1,0) & = & A(1,0,1) = A(0,1,1) = A(1,1) = 3 \\ A(1,1,1) & = & A(1,0,A(1,1,0)) = A(1,0,3) = A(3,3) = 61 \\ A(1,1,2) & = & A(1,0,61) = A(61,61) > 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 \\ A(1,1,3) & \approx & A(1,0,3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \approx 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \\ A(1,1,4) & \approx & A(1,0,3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \approx 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 \\ A(1,1,x) & \approx & 3 \rightarrow 3 \rightarrow x \rightarrow 2 \\ A(1,1,65) & \approx & 3 \rightarrow 3 \rightarrow 65 \rightarrow 2 > G \\ A(1,2,0) & = & A(1,1,1) = 61 \\ A(1,2,1) & = & A(1,1,61) > 3 \rightarrow 3 \rightarrow 61 \rightarrow 2 \\ A(1,2,2) & \approx & A(1,1,3 \rightarrow 3 \rightarrow 61 \rightarrow 2) > 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 61 \rightarrow 2) \rightarrow 2 > A(1,1,65) \end{eqnarray*}

よって、 A(1,2,2) > A(1,1,65) > グラハム数である。

コンウェイのチェーン表記との間との間には、次のような関係がある^[3]。

\(x=1, y>1\) または \(x>1, y+z>0\) のとき

\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1個の3} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]

すなわち、A(x,y,z)はx+3変数のチェーン表記と同程度の大きさとなり、A(1,0,1,2)はグラハム数の長さのチェーン表記を越える。

\begin{eqnarray*} A(1,0,1,0) & = & A(1,0,0,1) = A(1,0,1) = A(1,1) = 3 \\ A(1,0,1,1) & = & A(1,0,0,A(1,0,1,0)) \\ & = & A(1,0,0,3) = A(3,0,3) = A(2,3,3) \\ A(1,0,1,2) & = & A(1,0,0,A(1,0,1,1)) \\ & = & A(1,0,0,A(2,3,3)) \\ & = & A(A(2,3,3),0,A(2,3,3)) \approx \underbrace{3 \rightarrow 3 \rightarrow 3 ... 3 \rightarrow 3 \rightarrow 3}_{A(2,3,3)} \end{eqnarray*}

この関数の増加率は、急増加関数を使って次のように評価出来る。

\begin{eqnarray*} A(n, n) & \approx & f_{\omega}(n) \\ A(1, 0, n) & \approx & f_{\omega}(n) \\ A(a, 0, n) & \approx & f_{\omega･a}(n) \\ A(n, 0, n) & \approx & f_{\omega^2}(n) \\ A(1, 0, 0, n) & \approx & f_{\omega^2}(n) \\ A(a, 0, 0, n) & \approx & f_{\omega^2･a}(n) \\ A(n, 0, 0, n) & \approx & f_{\omega^3}(n) \\ A(1, 0, 0, 0, n) & \approx & f_{\omega^3}(n) \\ A(a, 0, 0, 0, n) & \approx & f_{\omega^3･a}(n) \\ A(n, 0, 0, 0, n) & \approx & f_{\omega^4}(n) \\ A(..., a3, a2, a1, a0, n) & \approx & f_{... + \omega^3･a3 + \omega^2･a2 + \omega･a1 + a0}(n) \\ A(\underbrace{1,1,...,1}_n) & \approx & f_{\omega^\omega}(n) \\ \end{eqnarray*}

他の記法による近似[]

\(A(..., d, c, b, a, n)\) は、次の様に近似される。

記法	近似
BEAF	\(\lbrace n,2,a+1,b+1,c+1,d+1,... \rbrace\)
急増加関数	\(f_{... \omega^3 d + \omega^2 c + \omega b + a}(n)\)
ハーディー階層	\(H_{\omega^{... \omega^3 d + \omega^2 c + \omega b + a} }(n)\)