Fandom

巨大数研究 Wiki

多変数アッカーマン関数

549このwikiの
ページ数
新しいページをつくる
コメント3 シェアする
多変数アッカーマン関数
基本関数 後者関数
急増加関数 \(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) > グラハム数 である。

A(x,y,z)はx+2変数のチェーン表記と同程度の大きさとなり、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)\)

参考サイト 編集

  1. 巨大数探索スレッド7@2ch数学板でアップされた文書 (たろう, 2007年10月17日)
  2. ふぃっしゅっしゅ (2013) 巨大数論

関連項目 編集

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki