アッカーマン関数

計算可能性理論 において、ヴィルヘルム・アッカーマンにちなんで名付けられたアッカーマン関数は、原始再帰的ではない全計算可能関数の最も単純で^[1]最も早く発見された例の1つです。すべての原始再帰関数は全計算可能で計算可能ですが、アッカーマン関数は、すべての全計算可能関数が原始再帰的であるとは限らないことを示しています。

アッカーマンが彼の関数（3つの非負の整数引数を持つ）^{[2]を発表した後、多くの著者がさまざまな目的に合わせてそれを修正したため、今日では「アッカーマン関数」は元の関数のさまざまなバリエーションのいずれかを指すことがあります。一般的なバージョンの1つは、}ロザ・ペーテルとラファエル・ロビンソンによって開発された2つの引数を持つアッカーマン・ペーテル関数です。その値は非常に急速に増加します。たとえば、は19,729桁の整数になります。 ^[3]${\displaystyle \operatorname {A} (4,2)}$${\displaystyle 2^{65536}-3}$

1920 年代後半、数学者ガブリエル・スーダンとヴィルヘルム・アッカーマンは、デイヴィッド・ヒルベルトの弟子で、計算の基礎を研究していました。スーダンとアッカーマンはともに、原始再帰的ではない全計算可能関数(いくつかの文献では単に「再帰的」と称される)を発見したとされています^[ 4] 。スーダンは、あまり知られていないスーダン関数を発表し、その後まもなく独立して、1928 年にアッカーマンが自身の関数(ギリシャ語の文字phiに由来) を発表しました。アッカーマンの 3 引数関数 は、 に対して、加算、乗算、累乗の基本演算を次のように 再現するように定義されます。 ${\displaystyle \varphi}$${\displaystyle \varphi (m,n,p)}$${\displaystyle p=0,1,2}$

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{aligned}}}$

p > 2の場合、これらの基本演算はハイパー演算と比較できる方法で拡張されます。

${\displaystyle {\begin{aligned}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{aligned}}}$

(完全に計算可能だが原始再帰的ではない関数としての歴史的な役割とは別に、アッカーマンの元の関数は、基本的な算術演算を累乗を超えて拡張すると考えられていますが、グッドスタインの ハイパー演算シーケンスなど、その目的のために特別に設計されたアッカーマン関数のバリアントほどシームレスではありません。)

デイヴィト・ヒルベルトは『無限について』^[5]でアッカーマン関数は原始再帰的ではないという仮説を立てたが、実際にその仮説を証明したのはヒルベルトの個人秘書で元教え子のアッカーマンであり、彼の論文『ヒルベルトの実数の構成について』^{[2] [6]}でその仮説を証明した。

その後、ロザ・ペーテル^[7]とラファエル・ロビンソン^[8]は、ほぼすべての著者に好まれるようになったアッカーマン関数の2変数バージョンを開発しました。

一般化されたハイパーオペレーションシーケンス（例えば）もアッカーマン関数の一種である。^[9]${\displaystyle G(m,a,b)=a[m]b}$

1963年にRCバックは、ハイパーオペレーションシーケンスに基づいた直感的な2変数^{[n 1]の}変種を考案した。^{[10] [11]}${\displaystyle \operatorname {F} }$

${\displaystyle \operatorname {F} (m,n)=2[m]n.}$

他のほとんどのバージョンと比較して、Buck 関数には不要なオフセットがありません。

${\displaystyle {\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\\&\quad \vdots \end{aligned}}}$

アッカーマン関数の他の多くのバージョンが研究されてきた。^{[12] [13]}

アッカーマンのオリジナルの3引数関数は、非負整数とに対して次のように再帰的に定義されます。 ${\displaystyle \varphi (m,n,p)}$${\displaystyle m,n,}$${\displaystyle p}$

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}}$

さまざまな 2 つの引数バージョンのうち、Péter と Robinson によって開発されたバージョン (ほとんどの著者によって「」Ackermann 関数と呼ばれています) は、非負の整数に対して次のように定義されます。 ${\displaystyle m}$${\displaystyle n}$

${\displaystyle {\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}}}$

アッカーマン関数はハイパーオペレーションシーケンスとの関連でも表現されている: ^{[14] [15]}

${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}$

または、Knuthの上矢印表記法（整数インデックスに拡張）で記述すると次のようになります。 ${\displaystyle \geq -2}$

${\displaystyle ={\begin{cases}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}}$

あるいは、バック関数Fの観点からは、次のように表される。^[10]

${\displaystyle ={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}$

を のn回目の反復として定義します。 ${\displaystyle f^{n}}$${\displaystyle f}$

${\displaystyle {\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\end{array}}}$

反復処理は、関数をそれ自身と特定の回数合成するプロセスです。関数合成は結合演算なので、 . ${\displaystyle f(f^{n}(x))=f^{n}(f(x))}$

アッカーマン関数を単項関数の列として考えると、 を設定できます。 ${\displaystyle \operatorname {A} _{m}(n)=\operatorname {A} (m,n)}$

関数は反復から定義される単項^{[n 2]}関数のシーケンスになります。 ${\displaystyle \operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...}$

${\displaystyle {\begin{array}{lcl}\operatorname {A} _{0}(n)&=&n+1\\\operatorname {A} _{m+1}(n)&=&\operatorname {A} _{m}^{n+1}(1)\\\end{array}}}$

アッカーマン関数の再帰定義は、項書き換えシステム (TRS)に自然に転置できます。

2元アッカーマン関数の定義は明らかな簡約規則を導く^{[16] [17]}

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r2)}}&A(S(m),0)&\rightarrow &A(m,S(0))\\{\text{(r3)}}&A(S(m),S(n))&\rightarrow &A(m,A(S(m),n))\end{array}}}$

例

計算${\displaystyle A(1,2)\rightarrow _{*}4}$

縮約シーケンスは^{[n 3]である。}

を計算するには、最初に要素を含むスタックを使用できます。 ${\displaystyle \operatorname {A} (m,n)}$${\displaystyle \langle m,n\rangle }$

その後、上位2つの要素が規則に従って繰り返し置き換えられる^{[n 4]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&n&\rightarrow &(n+1)\\{\text{(r2)}}&(m+1)&,&0&\rightarrow &m&,&1\\{\text{(r3)}}&(m+1)&,&(n+1)&\rightarrow &m&,&(m+1)&,&n\end{array}}}$

図式的には、次のように始まります。 ${\displaystyle \langle m,n\rangle }$

スタック長 <> 1 の場合
{
   2つの要素
   をPOPし、ルールr1、r2、r3を適用して1つまたは2つまたは3つの要素をPUSHする
}

疑似コードはGrossman & Zeitman (1988) に掲載されています。

たとえば、入力では、 ${\displaystyle \langle 2,1\rangle }$

備考

• 最左内戦略は、Rosetta Code上の 225 のコンピュータ言語で実装されています。
• の計算にはステップしかかかりません。^[18]${\displaystyle m,n}$${\displaystyle A(m,n)}$${\displaystyle (A(m,n)+1)^{m}}$
• Grossman & Zeitman (1988) は、 の計算において、である限り、スタックの最大長は であることを指摘しました。${\displaystyle \operatorname {A} (m,n)}$${\displaystyle \operatorname {A} (m,n)}$${\displaystyle m>0}$

独自のアルゴリズムは本質的に反復的であり、時間と空間内で計算を行います。${\displaystyle \operatorname {A} (m,n)}$${\displaystyle {\mathcal {O}}(m\operatorname {A} (m,n))}$${\displaystyle {\mathcal {O}}(m)}$

反復1項アッカーマン関数の定義は、異なる簡約規則につながる。

${\displaystyle {\begin{array}{lll}{\text{(r4)}}&A(S(0),0,n)&\rightarrow &S(n)\\{\text{(r5)}}&A(S(0),S(m),n)&\rightarrow &A(S(n),m,S(0))\\{\text{(r6)}}&A(S(S(x)),m,n)&\rightarrow &A(S(0),m,A(S(x),m,n))\end{array}}}$

関数合成は結合的であるため、規則r6の代わりに次のように定義できる。

${\displaystyle {\begin{array}{lll}{\text{(r7)}}&A(S(S(x)),m,n)&\rightarrow &A(S(x),m,A(S(0),m,n))\end{array}}}$

前のセクションと同様に、の計算はスタックを使用して実装できます。 ${\displaystyle \operatorname {A} _{m}^{1}(n)}$

最初、スタックには 3 つの要素が含まれます。 ${\displaystyle \langle 1,m,n\rangle }$

その後、上位3つの要素が規則に従って繰り返し置き換えられる^{[n 4]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}}$

図式的には、次のように始まります。 ${\displaystyle \langle 1,m,n\rangle }$

スタック長 <> 1 の場合
{
   3 つの要素
   を POP します。ルール r4、r5、r6 を適用して、1 つまたは 3 つまたは 5 つの要素をPUSH します。
}

例

入力時に連続するスタック構成は ${\displaystyle \langle 1,2,1\rangle }$

${\displaystyle {\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r6}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r6}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r6}1,0,{\underline {3,0,1}}\rightarrow _{r6}1,0,1,0,{\underline {2,0,1}}\\&\rightarrow _{r6}1,0,1,0,1,0,{\underline {1,0,1}}\rightarrow _{r4}1,0,1,0,{\underline {1,0,2}}\rightarrow _{r4}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$

対応する等式は

${\displaystyle {\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1))=A_{0}(A_{0}(A_{0}^{2}(1)))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1))))=A_{0}(A_{0}(A_{0}(2)))=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}}$

ルールr6の代わりにルールr7が使用される場合、スタック内の置換は次のようになります。

${\displaystyle {\begin{array}{lllllllll}{\text{(r7)}}&(x+2)&,m&,n&\rightarrow &(x+1)&,m&,1&,m&,n\end{array}}}$

その後のスタック構成は

${\displaystyle {\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r7}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r7}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r7}3,0,{\underline {1,0,1}}\rightarrow _{r4}{\underline {3,0,2}}\\&\rightarrow _{r7}2,0,{\underline {1,0,2}}\rightarrow _{r4}{\underline {2,0,3}}\rightarrow _{r7}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}}$

対応する等式は

${\displaystyle {\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1))=A_{0}^{3}(2)\\&=A_{0}^{2}(A_{0}(2))=A_{0}^{2}(3)=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}}$

備考

• これまで紹介した TRS は、任意の入力に対して同じステップ数で収束します。また、同じ削減ルールを使用します (この比較では、ルール r1、r2、r3 は、それぞれルール r4、r5、r6/r7 と同じと見なされます)。たとえば、の削減は14 ステップで収束します: 6 × r1、3 × r2、5 × r3。の削減も同じ 14 ステップで収束します: 6 × r4、3 × r5、5 × r6/r7。TRS は、削減ルールが適用される順序が異なります。${\displaystyle A(2,1)}$${\displaystyle A_{2}(1)}$
• が規則 {r4, r5, r6} に従って計算される場合、スタックの最大長は 未満に留まります。規則 r6 の代わりに削減規則 r7 を使用すると、スタックの最大長は のみになります。スタックの長さは再帰の深さを反映します。規則 {r4, r5, r7} に従った削減では再帰の最大深さがより小さくなるため、^{[n 6]}この計算はその点でより効率的です。${\displaystyle A_{i}(n)}$${\displaystyle 2\times A(i,n)}$${\displaystyle 2(i+2)}$

Sundblad (1971) や Porto & Matos (1980) が明示したように、アッカーマン関数はハイパーオペレーションシーケンスで表現できます。

${\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}$

または、定数2をパラメータリストから削除した後、バック関数の観点から

${\displaystyle ={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}$

バック関数[ ^10]はアッカーマン関数の変形であり、以下の簡約規則で計算できる。 ${\displaystyle \operatorname {F} (m,n)=2[m]n}$

${\displaystyle {\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}}$

ルールb6の代わりにルールを定義することもできる。

${\displaystyle {\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}}$

アッカーマン関数を計算するには、3つの簡約規則を追加するだけで十分である。

${\displaystyle {\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}}&P(S(S(S(m))))&\rightarrow &m\\\end{array}}}$

これらのルールは、基本ケース A(0,n)、アライメント (n+3)、およびファッジ (-3) を処理します。

例

計算${\displaystyle A(2,1)\rightarrow _{*}5}$

対応する等式は

• 削減規則を伴うTRSを適用すると、次のようになります。${\displaystyle {\text{b6}}}$

${\displaystyle {\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F(0,F^{5}(0,2))=F(0,F(0,F^{4}(0,2)))\\&=F(0,F(0,F(0,F^{3}(0,2))))=F(0,F(0,F(0,F(0,F^{2}(0,2)))))=F(0,F(0,F(0,F(0,F(0,F(0,2))))))\\&=F(0,F(0,F(0,F(0,F(0,3)))))=F(0,F(0,F(0,F(0,4))))=F(0,F(0,F(0,5)))=F(0,F(0,6))=F(0,7)=8\end{aligned}}}$

• 削減規則を伴うTRSを適用すると、次のようになります。${\displaystyle {\text{b7}}}$

${\displaystyle {\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F^{5}(0,F(0,2))=F^{5}(0,3)=F^{4}(0,F(0,3))=F^{4}(0,4)\\&=F^{3}(0,F(0,4))=F^{3}(0,5)=F^{2}(0,F(0,5))=F^{2}(0,6)=F(0,F(0,6))=F(0,7)=8\end{aligned}}}$

備考

• の計算は、{b1 - b5, b6, r8 - r10} という規則に従って、深く再帰的です。ネストされた の最大深度は です。原因は反復が実行される順序にあります。最初のものは、シーケンス全体が展開された後にのみ消えます。${\displaystyle \operatorname {A} _{i}(n)}$${\displaystyle F}$${\displaystyle A(i,n)+1}$${\displaystyle F^{n+1}(x)=F(F^{n}(x))}$${\displaystyle F}$
• その点では、{b1 - b5, b7, r8 - r10} の規則に従った計算の方が効率的です。反復は、コードブロックの繰り返しループをシミュレートします。^{[n 7]}ネストには、反復関数ごとに 1 つの再帰レベルという制限があります。Meyer & Ritchie (1967) はこの対応を示しました。${\displaystyle F^{n+1}(x)=F^{n}(F(x))}$${\displaystyle (i+1)}$
• これらの考慮事項は、再帰の深さにのみ関係します。どちらの方法で反復しても、同じ数の削減ステップがもたらされ、同じルールが適用されます (ルール b6 と b7 が「同じ」と見なされる場合)。たとえば、の削減は 35 ステップで収束します: 12 × b1、4 × b2、1 × b3、4 × b5、12 × b6/b7、1 × r9、1 × r10。反復法は、削減ルールが適用される順序にのみ影響します。${\displaystyle A(2,1)}$
• 実行時間の実際の短縮は、サブ結果を何度も再計算しないことによってのみ達成できます。メモ化は、関数呼び出しの結果をキャッシュし、同じ入力が再び発生したときに返す最適化手法です。たとえば、Ward (1993) を参照してください。Grossman と Zeitman (1988) は、時間と空間内で計算する巧妙なアルゴリズムを公開しました。${\displaystyle A(i,n)}$${\displaystyle {\mathcal {O}}(iA(i,n))}$${\displaystyle {\mathcal {O}}(i)}$

計算が多くのステップと大きな数値でどのように行われるかを示すために：^{[n 5]}${\displaystyle A(4,3)}$

${\displaystyle {\begin{aligned}A(4,3)&\rightarrow A(3,A(4,2))\\&\rightarrow A(3,A(3,A(4,1)))\\&\rightarrow A(3,A(3,A(3,A(4,0))))\\&\rightarrow A(3,A(3,A(3,A(3,1))))\\&\rightarrow A(3,A(3,A(3,A(2,A(3,0)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,4)))))\\&\rightarrow A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}}$

アッカーマン関数の計算は、無限の表で言い換えることができます。まず、自然数を一番上の行に並べます。表の数字を決定するには、すぐ左の数字を取ります。次に、その数字を使用して、その数字で指定された列と 1 行上の列で必要な数字を検索します。その左側に数字がない場合は、前の行の見出しが「1」の列を参照するだけです。表の左上の小さな部分を次に示します。

ここで再帰的指数またはKnuth 矢印のみで表現される数値は非常に大きく、単純な 10 進数で表記するにはスペースを取りすぎます。

表のこの最初のセクションでは大きな値が出現しますが、グラハム数など、さらに大きな数も定義されています。グラハム数は、クヌース矢印の数が少ないと表すことができません。この数は、アッカーマン関数を自身に再帰的に適用するのと同様の手法で構築されます。

これは上記の表の繰り返しですが、パターンを明確に示すために、値が関数定義の関連する式に置き換えられています。

• の評価が常に終了することは、すぐには明らかではないかもしれません。ただし、各再帰アプリケーションで が減少するか、同じままで減少するため、再帰は制限されます。 がゼロに達するたびに が減少し、最終的に もゼロに達します。(より技術的に表現すると、各ケースでペアはペアの辞書式順序で減少します。これは、単一の非負整数の順序と同様に、整列したです。つまり、順序が無限に連続して下がることはできません。) ただし、が減少する場合、増加できる量に上限はなく、多くの場合大幅に増加します。${\displaystyle A(m,n)}$${\displaystyle m}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$${\displaystyle m}$${\displaystyle m}$${\displaystyle (m,n)}$${\displaystyle m}$${\displaystyle n}$
• mが1、2、3 のように小さい値の場合、アッカーマン関数はnに対して比較的ゆっくりと増加します(最大でも指数関数的に増加します)。ただし、 の場合は、はるかに急速に増加します。m は、約 2.00353 × 10です。${\displaystyle m\geq 4}$${\displaystyle A(4,2)}$^{19 728}であり、 の小数展開は、あらゆる典型的な尺度で見て非常に大きく、約 2.12004 × 10 ^{6.03123 × 10}${\displaystyle A(4,3)}$^{19 727} .
• 興味深い点は、このプログラムが使用する算術演算は 1 の加算だけであるということです。このプログラムの急速なパワー増大は、ネストされた再帰のみに基づいています。これは、実行時間が少なくとも出力に比例し、非常に膨大になることも意味します。実際には、ほとんどの場合、実行時間は出力よりもはるかに長くなります (上記を参照)。
• と の両方を同時に増加させる単一引数バージョンは、指数関数 、階乗関数、多重階乗関数および超階乗関数、さらには Knuth の上矢印表記法を使用して定義された関数 (インデックス付き上矢印が使用されている場合を除く) などの非常に増加の速い関数を含む、すべての原始再帰関数を小さく見せます。 は、増加の速い階層でとほぼ同等であることがわかります。 この極端な増加を利用して、 はチューリングマシンなどの無限のメモリを持つマシンで明らかに計算可能であり、したがって計算可能関数であるが、どの原始再帰関数よりも速く増加し、したがって原始再帰ではないことを示すことができます。${\displaystyle f(n)=A(n,n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle f_{\omega }(n)}$${\displaystyle f}$

アッカーマン関数は、どの原始再帰関数よりも速く増加するため、それ自体は原始再帰的ではありません。証明の概要は次のとおりです。最大 k 回の再帰を使用して定義された原始再帰関数は、高速増加階層の (k+1) 番目の関数である よりも遅く増加する必要がありますが、アッカーマン関数は少なくとも と同じ速さで増加します。 ${\displaystyle f_{k+1}(n)}$${\displaystyle f_{\omega }(n)}$

具体的には、すべての原始再帰関数に対して、すべての非負整数に対して、 ${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle t}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i}).}$

これが確立されると、それ自体は原始再帰的ではないことが分かります。そうでなければ、${\displaystyle A}$${\displaystyle x_{1}=x_{2}=t}$${\displaystyle A(t,t)<A(t,t).}$

証明は次のように進む：アッカーマン関数よりも遅く増加するすべての関数の クラスを定義する${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {A}}=\left\{f\,{\bigg |}\,\exists t\ \forall x_{1}\cdots \forall x_{n}:\ f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i})\right\}}$

そして、 がすべての原始再帰関数を含むことを示します。 後者は、 が定数関数、後続関数、射影関数を含み、関数合成と原始再帰の操作に対して閉じていることを示すことによって達成されます。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

アッカーマン関数は、ベクトル加算システム^[20]やペトリネット到達可能性^[21]などのいくつかのアルゴリズム^[19]の時間計算量に現れ、大規模なインスタンスでは計算不可能であることを示しています。アッカーマン関数の逆関数は、いくつかの時間計算量結果に現れます。

上で考察した関数f ( n ) = A ( n , n )は非常に急速に増加するため、その逆関数f −1^は非常にゆっくりと増加します。この逆アッカーマン関数f ^{−1は通常}αで表されます。実際、A (4, 4)は のオーダーであるため、 α ( n ) は任意の実用的な入力サイズnに対して 5 未満です。   ${\displaystyle 2^{2^{2^{2^{16}}}}}$

この逆関数は、分離集合データ構造や最小全域木に対するChazelleのアルゴリズムなど、一部のアルゴリズムの時間計算量に現れます。これらの設定では、Ackermann の元の関数やその他のバリエーションが使用されることもありますが、それらはすべて同様に高い速度で増加します。特に、いくつかの修正された関数は、-3 などの項を削除することで式を簡素化します。

逆アッカーマン関数の2パラメータ変形は次のように定義できます。ここで、 は床関数です。 ${\displaystyle \lfloor x\rfloor }$

${\displaystyle \alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.}$

この関数は、上記のアルゴリズムをより正確に分析する際に発生し、より洗練された時間制限を与えます。分離集合データ構造では、m は演算数を表し、nは要素数を表します。最小全域木アルゴリズムでは、m は辺の数を表し、n は頂点の数を表します。α ( m , n )には、わずかに異なる定義がいくつかあります。たとえば、log ₂ n はnに置き換えられることがあり、床関数は天井関数に置き換えられることがあります。

他の研究では、mを定数に設定して1の逆関数を定義し、その逆が特定の行に適用されるかもしれない。^[22]

アッカーマン関数の逆関数は原始再帰的である。^[23]

アッカーマン関数は、非常に深い再帰に基づいて定義されているため、コンパイラの再帰最適化能力のベンチマークとして使用できます。この方法でアッカーマン関数を初めて公開したのは、1970年にDragoșVaida ^[24]と、ほぼ同時に1971年にYngve Sundblad ^{[14]です。}

サンドブラッドの画期的な論文は、ブライアン・ヴィッヒマン（ウェットストーンベンチマークの共著者）によって1975年から1982年にかけて書かれた三部作の論文の中で取り上げられました。 ^{[25] [26] [27]}

• 計算可能性理論
• 二重再帰
• 急速に成長する階層
• グッドスタイン関数
• 原始再帰関数
• 再帰（コンピュータサイエンス）

• 「アッカーマン関数」。数学百科事典。EMS Press。2001 [1994]。
• Weisstein, Eric W.「アッカーマン関数」。MathWorld。
•  この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「Ackermann 関数」。アルゴリズムとデータ構造の辞書。NIST 。
• アニメーション化されたアッカーマン関数計算機
• アーロンソン、スコット(1999)。「より大きな数字を挙げられるのは誰か?」
• アッカーマン関数。いくつかの値の表が含まれています。
• ブルーベーカー、ベン（2023年12月4日）。「簡単に聞こえる問題が、私たちの宇宙には大きすぎる数字を生み出す」。
• ムナフォ、ロバート。「大きな数字」。Aの定義に関するいくつかのバリエーションについて説明します。
• Nivasch, Gabriel (2021年10月). 「痛みのない逆アッカーマン」。2007年8月21日時点のオリジナルよりアーカイブ。2023年6月18日閲覧。
• Seidel, Raimund. 「逆アッカーマン関数の理解」(PDF)。
• さまざまなプログラミング言語で書かれたアッカーマン関数 ( Rosetta Code上)
• Smith, Harry J. 「Ackermann's Function」。2009年10月26日時点のオリジナルよりアーカイブ。) 少し勉強してプログラミングをします。