巨大数研究 Wiki
Advertisement
巨大数研究 Wiki
多変数アッカーマン関数
基本関数 後者関数
急増加関数 \(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)\)

参考サイト

関連項目

日本の巨大数論

Aeton: おこじょ数N成長階層
mrna: 段階配列表記降下段階配列表記多変数段階配列表記横ネスト段階配列表記
Kanrokoti: くまくまψ関数亜原始ψ関数ハイパー原始ψ関数TSS-ψ関数
クロちゃん: 第一クロちゃん数第二クロちゃん数第三クロちゃん数第四クロちゃん数
たろう: 多変数アッカーマン関数2重リストアッカーマン関数多重リストアッカーマン関数
Nayuta Ito: フラン数N原始東方巨大数4の規則の境界を突いた巨大数
バシク: 原始数列数ペア数列数バシク行列システム
長谷川由紀路: 紅魔館のメイドナンバー恋符マスタースパーク数みくみく順序数
108Hassium: E2:B-01-HsE3:B-02-Hs
公太郎: 弱亜ペア数列肉ヒドラ数列弱ハイパーペア数列
p進大好きbot: 超限急増加関数表記拡張ブーフホルツのψ関数に伴う順序数表記四関数三関数巨大数庭園数
ふぃっしゅ: ふぃっしゅ数バージョン1バージョン2バージョン3バージョン4バージョン5バージョン6バージョン7マシモ関数マシモスケールTR関数I0関数
ゆきと: 亜原始数列ハイパー原始数列Y数列
本: 巨大数論寿司虚空編
大会: 東方巨大数幻想巨大数即席巨大数式神巨大数
掲示板: 巨大数探索スレッド名もなき巨大数研究
外部リンク: 日本語の巨大数関連サイト


Advertisement