アッカーマン関数

Quickly growing function

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

アッカーマンが自身の関数（3つの非負整数引数を持つ）^{[2]を発表した後、多くの著者が様々な目的に合わせてこの関数を改良したため、今日では「アッカーマン関数」は元の関数の様々な変種を指すこともあります。一般的なバージョンの一つは、}ロザ・ペーテルとラファエル・ロビンソンによって開発された2引数のアッカーマン・ペーテル関数です。この関数は、適切な基本ケースを持つ漸化式から定義されます。その値は非常に急速に増加します。例えば、は19,729桁の整数となります。 ^[3] $\operatorname {A} (m+1,n+1)=\operatorname {A} (m,\operatorname {A} (m+1,n))$ $\operatorname {A} (4,2)$ $2^{65536}-3$

歴史

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

${\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$

${\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] $G(m,a,b)=a[m]b$

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

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

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

${\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引数関数は、非負整数とに対して次のように再帰的に定義されます。 $\varphi (m,n,p)$ $m,n,$ $p$

${\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 関数と呼ばれています) は、非負の整数に対して次のように定義されます。 $m$ $n$

${\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]

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

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

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

あるいは、バック関数Fの観点からは：^[10]

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

について帰納的に考えると、すべてのに対してであることが証明できる。 $m$ $F(m,n)\leq A(m,n)$ $m,n\in \mathbb {N} _{0}$

定義: 反復1項関数として

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

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

反復処理とは、関数を自身と一定回数合成する処理です。関数合成は結合法則に従うため、. $f(f^{n}(x))=f^{n}(f(x))$

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

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

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

計算

LOOPプログラムによる計算

これらの関数は、（有限レベルの）高速増加階層（FGH）関数に適合する^[16] $\operatorname {A} _{i}$

{\begin{array}{lcl}\operatorname {FGH} _{0}(n)&=&n+1\\\operatorname {FGH} _{m+1}(n)&=&\operatorname {FGH} _{m}^{n}(n)\,.\end{array}}

次の不等式が成り立つ：^[17] $\forall m>1,\forall n>1:\operatorname {A} _{m}(n)<\operatorname {FGH} _{m}(n)$

固定の場合、関数はネストの深さのLOOPプログラムによって計算できます。^[18] $k$ $\operatorname {FGH} _{k}(n)$ $k$

# 入力 (n)
ループ n :                   # ネストの深さ: 1
    ループ n :               # ネストの深さ: 2 
        ...               # ...
            ループ n :       # ネストの深さ: k 
                n  +=  1    # 
# 出力 (n)

この関数はLOOP-kプログラムによって計算することもできる。^[19]（プログラム（スキーマ）はここには記載されていない。） $\operatorname {A} _{k}(n)$

は原始的な再帰関数ではないため（下記参照）、LOOP プログラムでは計算できないことは明らかです。 $\operatorname {A} (m,n)$

2項関数に基づく項書き換えシステムによる計算

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

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

${\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}}$

例

コンピューティング $A(1,2)\rightarrow _{*}4$

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

最左最外（ワンステップ）戦略：	最左最内（ワンステップ）戦略：
${\underline {A(S(0),S(S(0)))}}$	${\underline {A(S(0),S(S(0)))}}$
$\rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})$
$\rightarrow _{r1}S({\underline {A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))$
$\rightarrow _{r3}S({\underline {A(0,A(S0,0))}})$	$\rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))$
$\rightarrow _{r1}S(S({\underline {A(S(0),0)}}))$	$\rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})$
$\rightarrow _{r2}S(S({\underline {A(0,S(0))}}))$	$\rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}$
$\rightarrow _{r1}S(S(S(S(0))))$	$\rightarrow _{r1}S(S(S(S(0))))$

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

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

${\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}}$

図式的に言えば、次のようになります: $\langle m,n\rangle$

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

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

例えば、入力では、 $\langle 2,1\rangle$

スタック構成	減少を反映する^{[n 5]}
${\underline {2,1}}$	${\underline {A(2,1)}}$
$\rightarrow 1,{\underline {2,0}}$	$\rightarrow _{r1}A(1,{\underline {A(2,0)}})$
$\rightarrow 1,{\underline {1,1}}$	$\rightarrow _{r2}A(1,{\underline {A(1,1)}})$
$\rightarrow 1,0,{\underline {1,0}}$	$\rightarrow _{r3}A(1,A(0,{\underline {A(1,0)}}))$
$\rightarrow 1,0,{\underline {0,1}}$	$\rightarrow _{r2}A(1,A(0,{\underline {A(0,1)}}))$
$\rightarrow 1,{\underline {0,2}}$	$\rightarrow _{r1}A(1,{\underline {A(0,2)}})$
$\rightarrow {\underline {1,3}}$	$\rightarrow _{r1}{\underline {A(1,3)}}$
$\rightarrow 0,{\underline {1,2}}$	$\rightarrow _{r3}A(0,{\underline {A(1,2)}})$
$\rightarrow 0,0,{\underline {1,1}}$	$\rightarrow _{r3}A(0,A(0,{\underline {A(1,1)}}))$
$\rightarrow 0,0,0,{\underline {1,0}}$	$\rightarrow _{r3}A(0,A(0,A(0,{\underline {A(1,0)}})))$
$\rightarrow 0,0,0,{\underline {0,1}}$	$\rightarrow _{r2}A(0,A(0,A(0,{\underline {A(0,1)}})))$
$\rightarrow 0,0,{\underline {0,2}}$	$\rightarrow _{r1}A(0,A(0,{\underline {A(0,2)}}))$
$\rightarrow 0,{\underline {0,3}}$	$\rightarrow _{r1}A(0,{\underline {A(0,3)}})$
$\rightarrow {\underline {0,4}}$	$\rightarrow _{r1}{\underline {A(0,4)}}$
$\rightarrow 5$	$\rightarrow _{r1}5$

備考

最左内戦略は、Rosetta Code上の 225 のコンピュータ言語で実装されています。
の計算にはステップしかかかりません。^[22] $m,n$ $A(m,n)$ $(A(m,n)+1)^{m}$
Grossman & Zeitman (1988) は、の計算において、である限り、スタックの最大長はであることを指摘しました。 $\operatorname {A} (m,n)$ $\operatorname {A} (m,n)$ $m>0$
独自のアルゴリズムは本質的に反復的であり、時間と空間内で計算を行います。 $\operatorname {A} (m,n)$ ${\mathcal {O}}(m\operatorname {A} (m,n))$ ${\mathcal {O}}(m)$

反復1項関数に基づくTRSによる計算

反復1元アッカーマン関数の定義は、異なる簡約規則を導く。

${\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の代わりに次のように定義できる。

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

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

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

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

${\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}}$

図式的に言えば、次のようになります: $\langle 1,m,n\rangle$

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

例

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

${\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}}$

対応する等式は

${\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が使用される場合、スタック内の置換は次のようになります。

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

その後のスタック構成は

${\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}}$

対応する等式は

${\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は、縮約規則が適用される順序が異なります。 $A(2,1)$ $A_{2}(1)$
を{r4, r5, r6}の規則に従って計算する場合、スタックの最大長は未満に留まります。規則r6の代わりに縮約規則r7を使用すると、スタックの最大長はのみになります。スタックの長さは再帰の深さを反映します。規則{r4, r5, r7}に従った縮約では再帰の最大深さが小さくなるため、^{[n 6]、}この計算はその点でより効率的です。 $A_{i}(n)$ $2\times A(i,n)$ $2(i+2)$

ハイパー演算子に基づくTRSによる計算

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

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

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

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

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

${\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の代わりに、次のルールを定義することもできる。

${\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}$ アッカーマン関数を計算するには、3つの簡約規則を追加するだけで十分である。

${\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) を処理します。

例

コンピューティング $A(2,1)\rightarrow _{*}5$

削減規則を使用する：^{[n 5]} ${\text{b7}}$	削減規則を使用する：^{[n 5]} ${\text{b6}}$
${\underline {A(2,1)}}$	${\underline {A(2,1)}}$
$\rightarrow _{r9}P({\underline {F(1,2,4)}})$	$\rightarrow _{r9}P({\underline {F(1,2,4)}})$
$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$	$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$
$\rightarrow _{b3}P({\underline {F(4,1,0)}})$	$\rightarrow _{b3}P({\underline {F(4,1,0)}})$
$\rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)}}))$	$\rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(3,1,2)}})$	$\rightarrow _{b6}P(F(1,1,F(1,1,{\underline {F(2,1,0)}})))$
$\rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b5}P(F(2,1,F(2,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(1,1,2)}})))$
$\rightarrow _{b2}P(F(2,1,{\underline {F(2,0,2)}}))$	$\rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b7}P(F(2,1,F(1,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(2,0,2)}})))$
$\rightarrow _{b1}P(F(2,1,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{\underline {F(1,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(2,1,4)}})$	$\rightarrow _{b1}P(F(1,1,F(1,1,{\underline {F(1,0,3)}})))$
$\rightarrow _{b7}P(F(1,1,{\underline {F(1,1,4)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)}}))$
$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$
$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$	$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$
$\rightarrow _{b7}P(F(1,1,F(3,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,{\underline {F(3,0,2)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{\underline {F(2,0,2)}}))))$
$\rightarrow _{b7}P(F(1,1,F(2,0,{\underline {F(1,0,3)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}})))))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4)}}))$	$\rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{\underline {F(1,0,3)}}))))$
$\rightarrow _{b7}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$	$\rightarrow _{b1}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$
$\rightarrow _{b1}P({\underline {F(1,1,6)}})$	$\rightarrow _{b1}P({\underline {F(1,1,6)}})$
$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$	$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(6,0,2)}})$	$\rightarrow _{b2}P({\underline {F(6,0,2)}})$
$\rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2)}}))$	$\rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)}}))$
$\rightarrow _{b1}P({\underline {F(5,0,3)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2)}})))$
$\rightarrow _{b7}P(F(4,0,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{\underline {F(3,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(4,0,4)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(2,0,2)}})))))$
$\rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}}))))))$
$\rightarrow _{b1}P({\underline {F(3,0,5)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,3)}})))))$
$\rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{\underline {F(1,0,4)}}))))$
$\rightarrow _{b1}P({\underline {F(2,0,6)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,{\underline {F(1,0,5)}})))$
$\rightarrow _{b7}P(F(1,0,{\underline {F(1,0,6)}}))$	$\rightarrow _{b1}P(F(1,0,{\underline {F(1,0,6)}}))$
$\rightarrow _{b1}P({\underline {F(1,0,7)}})$	$\rightarrow _{b1}P({\underline {F(1,0,7)}})$
$\rightarrow _{b1}{\underline {P(8)}}$	$\rightarrow _{b1}{\underline {P(8)}}$
$\rightarrow _{r10}5$	$\rightarrow _{r10}5$

対応する等式は

削減規則を伴うTRSを適用すると、 ${\text{b6}}$

${\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を適用すると、 ${\text{b7}}$

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

膨大な数

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

${\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」の列を見てください。表の左上の小さな部分を以下に示します。

A ( m , n ) の値
n メートル	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	2 ⁶⁵⁵³⁶ – 3	${2^{2^{65536}}}-3$	${2^{2^{2^{65536}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$
			$=2\uparrow \uparrow 5-3$ $\approx 2.00353\cdot {10^{19728}}$	$=2\uparrow \uparrow 6-3$	$=2\uparrow \uparrow 7-3$
				$=2\uparrow \uparrow 6-3$	$=2\uparrow \uparrow 7-3$	$=2\uparrow \uparrow (n+3)-3$
5	65533	$2\uparrow \uparrow 65536-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow 65536-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
メートル	$(2\uparrow ^{m-2}3)-3$	$(2\uparrow ^{m-2}4)-3$	$(2\uparrow ^{m-2}5)-3$	$(2\uparrow ^{m-2}6)-3$	$(2\uparrow ^{m-2}7)-3$	$(2\uparrow ^{m-2}(n+3))-3$

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

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

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

A ( m , n ) の値
n メートル	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A (0, 1)	A (0, A (1, 0)) = A (0, 2)	A (0, A (1, 1)) = A (0, 3)	A (0, A (1, 2)) = A (0, 4)	A (0, A (1, 3)) = A (0, 5)	A (0, A (1, n −1))
2	A（1, 1）	A (1, A (2, 0)) = A (1, 3)	A (1, A (2, 1)) = A (1, 5)	A (1, A (2, 2)) = A (1, 7)	A (1, A (2, 3)) = A (1, 9)	A (1, A (2, n −1))
3	A（2、1）	A (2, A (3, 0)) = A (2, 5)	A (2, A (3, 1)) = A (2, 13)	A (2, A (3, 2)) = A (2, 29)	A (2, A (3, 3)) = A (2, 61)	A (2, A (3, n −1))
4	A（3、1）	A (3, A (4, 0)) = A (3, 13)	A (3, A (4, 1)) = A (3, 65533)	A (3, A (4, 2))	A (3, A (4, 3))	A (3, A (4, n −1))
5	A（4、1）	A (4, A (5, 0))	A (4, A (5, 1))	A (4, A (5, 2))	A（4、A（5、3））	A (4, A (5, n −1))
6	A（5, 1）	A (5, A (6, 0))	A (5, A (6, 1))	A (5, A (6, 2))	A（5、A（6、3））	A (5, A (6, n −1))

プロパティ

一般的なコメント

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

原始再帰ではない

アッカーマン関数はどの原始再帰関数よりも速く増加するため、それ自体は原始再帰的ではありません。

証明スケッチ：

原始再帰関数は、合成と原始再帰を用いて基本関数から構築され、すべて一定の速度で成長します。全関数の階層を以下のように構成的に定義します。 $\operatorname {FGH} _{k}(n)$

$\operatorname {FGH} _{0}(n)=n+1,\quad \operatorname {FGH} _{k+1}(n)=\operatorname {FGH} _{k}^{n}(n)$

ここで、は入力に対するの - 倍の反復を表す。^[23]この階層構造はの増加とともに厳密に速く成長し、すべての原始再帰関数は最終的にによって上方に有界になる。これは原始再帰関数の定義に関する構造的帰納法によって示すことができる。 $\operatorname {FGH} _{k}^{n}$ $n$ $\operatorname {FGH} _{k}$ $n$ $k$ $\operatorname {FGH} _{k}$

しかし、アッカーマン関数は最終的に任意のを超えます。任意のに対して、十分に大きいに対してとなる関数が存在します。したがって、はどの原始再帰関数よりも速く増加するため、原始再帰関数ではありません。 $\operatorname {A} (m,n)$ $\operatorname {FGH} _{k}$ $k$ $m$ $\operatorname {A} (m,n)>\operatorname {FGH} _{k}(n)$ $n$ $\operatorname {A}$

逆

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

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

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

$\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に置き換えられる場合があり、floor 関数はceilingに置き換えられる場合があります。

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

アッカーマン関数の逆関数は原始再帰的である。なぜなら、それはグラフ原始再帰的であり、原始再帰関数によって上限が定められるからである。^[25]

使用法

計算の複雑さにおいて

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

アッカーマン関数の逆関数は、いくつかの時間計算量結果に現れる。例えば、分離集合データ構造は、演算ごとに逆アッカーマン関数に比例した償却時間を要し^{[29] 、計算量}セルプローブモデルの範囲内でこれを高速化することは不可能である^[30]。

離散幾何学では

離散幾何学におけるダベンポート・シンツェル列に関連する特定の問題には、逆アッカーマン関数が現れる計算量限界が存在する。例えば、平面上の線分の場合、線分の配置の非有界面は計算量を持ち、また線分系の中には計算量の非有界面を持つものがある。^[31] $\alpha (n)$ $n$ $O(n\alpha (n))$ $n$ $\Omega (n\alpha (n))$

ベンチマークとして

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

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

参照

注記

^ パラメータの順序を逆にした
^ 「カレー風味」
^ 各ステップで下線部のredexが書き換えられます。
^ ab ここ: 左端から内側への戦略!
^ abcd 読みやすくするために
、S(0) は 1 と表記され、
S(S(0)) は 2 と表記され、
S(S(S(0))) は 3 と表記されます
。
^ 再帰の最大深度とは、ある手続きの最も深い呼び出し時に存在する、その手続きの活性化の階層数を指す。Cornelius & Kirby (1975)
^ n+1回ループするDO F

参考文献

^ モナンとヒンシェイ、2003、p. 61.
^ ab アッカーマン 1928。
^ “A(4,2)の10進展開”. kosara.net . 2000年8月27日. 2010年1月20日時点のオリジナルよりアーカイブ。
^ カルード、マーカス＆テヴィ 1979.
^ ヒルベルト 1926年、185ページ。
^ ヴァン・ヘイジェノールト 1977.
^ ピーター 1935.
^ ロビンソン 1948.
^ リッチー1965年、1028ページ。
^ abc Buck 1963.
^ Meeussen & Zantema 1992、p. 6.
^ ムナフォ 1999a.
^ リッチー 1965年。
^ ab Sundblad 1971より。
^ ポルト＆マトス 1980.
^ オディフレディ 1999、298ページ。
^ 「アッカーマン階層と急成長階層」。StackExchange。
^ Pythonと同様に、オフサイドルール( INDENT ... DEDENT )
に従ったインデント:
```
 範囲( n )内の_ の場合: n += 1  
      
```
^ マイヤー＆リッチー 1967年。
^ グロスマン＆ツァイトマン 1988.
^ ポールソン 2021.
^ Cohen 1987、p. 56、命題3.16（証明を参照）。
^ グジェゴルチク階層を定義する別の関数列は、原始再帰関数を「成長クラス」に分割するために頻繁に使用されます。ただし、（または）とは添字が一致しません。 $\operatorname {E} _{n}$ $\operatorname {FGH} _{n}$ $\operatorname {A} _{n}$ $\operatorname {E} _{n}$
^ ペティ 2002年。
^ マトス 2014.
^ ブルベーカー 2023.
^ チェルヴィンスキー & オルリコウスキー 2022.
^ ルルー 2022年。
^ タージャン 1975.
^ フレッドマン＆サックス 1989.
^ Wiernik & Sharir 1988.
^ ヴァイダ 1970.
^ ヴィッヒマン 1976.
^ ヴィッヒマン 1977.
^ ヴィッヒマン 1982.

参考文献

アッカーマン、ヴィルヘルム(1928)。「Zum Hilbertschen Aufbau der reellen Zahlen」[実数のヒルベルト的構築について]。Mathematische Annalen (ドイツ語)。99 : 118–133。土井:10.1007/BF01459088。S2CID 123431274。
Buck, RC (1963). 「数学的帰納法と再帰的定義」. American Mathematical Monthly . 70 (2): 128– 135. doi :10.2307/2312881. JSTOR 2312881.
カルード, クリスチャン;マーカス, ソロモン; テヴィ, イオネル (1979年11月). 「原始再帰関数ではない再帰関数の最初の例」. Historia Math. 6 (4): 380–84 . doi : 10.1016/0315-0860(79)90024-7 .
コーエン、ダニエル・E.（1987年1月）『計算可能性と論理』ハルステッド・プレス、ISBN 9780745800349。
コーネリアス, BJ; カービー, GH (1975). 「再帰の深さとアッカーマン関数」. BIT数値数学. 15 (2): 144– 150. doi :10.1007/BF01932687. S2CID 120532578.
Czerwiński, Wojciech; Orlikowski, Łukasz (2022年2月7日).ベクトル加算システムにおける到達可能性はアッカーマン完全である. Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. arXiv : 2104.13866 . doi :10.1109/FOCS52979.2021.00120.
Fredman, M. ; Saks, M. (1989年5月). 「動的データ構造のセルプローブ計算量」.第21回ACM計算理論シンポジウム (STOC '89) の議事録. pp. 345– 354. doi : 10.1145/73007.73040 . ISBN 0897913078. S2CID 13470414。
Grossman, Jerrold W.; Zeitman, R. Suzanne (1988年5月). 「アッカーマン関数の本質的に反復的な計算」.理論計算機科学. 57 ( 2–3 ): 327– 330. doi :10.1016/0304-3975(88)90046-1.
ヴァン・ヘイエノールト、ジャン（1977）[訂正を加えて再版、初版1967年]『フレーゲからゲーデルへ：1879年から1931年までの数学論理学の原典』ハーバード大学出版局。
デイヴィッド・ヒルベルト(1926)。「Über das Unendliche」[無限について]。Mathematische Annalen (ドイツ語)。95 : 161–190。土井:10.1007/BF01206605。S2CID 121888793。
ルルー, ジェローム (2022年2月7日).ペトリネットの到達可能性問題は原始再帰的ではない. 2021 IEEE 第62回コンピュータサイエンス基礎シンポジウム議事録. arXiv : 2104.12695 . doi :10.1109/FOCS52979.2021.00121.
スイス、ロブ。ウェイナー、SS (1970)。「数論的関数の階層 I.」。数学ロジックとグルンドラーゲンフォルシュングのアーカイブ。13 ( 1–2 ): 39–51 .土井:10.1007/BF01967649。
Matos, Armando B (2014年5月7日). 「アッカーマン関数の逆関数は原始再帰的である」(PDF) . 2022年10月9日時点のオリジナルよりアーカイブ(PDF) 。
Meeussen, VCS; Zantema, H. (1992). 自然数の解釈に基づく項書き換えにおける導出長(PDF) (レポート). ユトレヒト大学コンピュータサイエンス学部. ISSN 0924-3275. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) 。
マイヤー、アルバート・R.；リッチー、デニス・マカリスター(1967). 「ループプログラムの計算量」. 1967年第22回全国会議議事録. ACM '67: 1967年第22回全国会議議事録. pp. 465– 469. doi : 10.1145/800196.806014 .
モナン、ジャン＝フランソワ、ヒンチー、MG（2003年）『形式手法の理解』シュプリンガー、p.61、ISBN 9781852332471。
Munafo, Robert (1999a). 「アッカーマン関数のバージョン」. MROBのLarge Numbers . 2021年11月6日閲覧。
ムナフォ、ロバート (1999b). 「新しい演算子と関数の発明」. MROBにおける大きな数. 2021年11月6日閲覧。
オディフレッディ、ピエールジョルジオ(1999).古典的再帰理論. 第2巻. 論理学と数学の基礎研究. 第143巻. アムステルダム: 北ホラント. ISBN 978-0-444-50205-6. MR 1718169。
ポールソン、ローレンス・C. (2021). 「反復形式におけるアッカーマン関数：証明支援実験」2021年10月19日閲覧。
ペテル、ロザ(1935)。 "Konstruktion nichtrekursiver Funktionen" [非再帰関数の構築]。Mathematische Annalen (ドイツ語)。111 : 42–60 .土井:10.1007/BF01472200。S2CID 121107217。
Pettie, S. (2002). 「オンライン最小全域木検証問題に対する逆アッカーマン法による下限値」.第43回IEEEコンピュータサイエンス基礎シンポジウム, 2002. Proceedings . pp. 155– 163. doi :10.1109/SFCS.2002.1181892. ISBN 0-7695-1822-2. S2CID 8636108。
Porto, António; Matos, Armando B. (1980年9月1日). 「Ackermannと超大国」(PDF) . ACM SIGACT News . 12 (3): 90– 95. doi :10.1145/1008861.1008872. S2CID 29780652. 2022年10月9日時点のオリジナルよりアーカイブ(PDF) .オリジナル版は1980年にACM SIGACT Newsに掲載され、2012年10月20日と2016年1月23日に改訂されました（ワーキングペーパー）
リッチー、ロバート・ウェルズ (1965年11月). 「アッカーマン関数に基づく再帰関数のクラス」.パシフィック・ジャーナル・オブ・マスマティクス. 15 (3): 1027–1044 . doi : 10.2140/pjm.1965.15.1027 .
ロビンソン、ラファエル・ミッチェル(1948). 「再帰と二重再帰」.アメリカ数学会報. 54 (10): 987–93 . doi : 10.1090/S0002-9904-1948-09121-2 .
Sundblad, Yngve (1971年3月). 「アッカーマン関数：理論、計算、そして数式操作による研究」. BIT Numerical Mathematics . 11 (1): 107– 119. doi :10.1007/BF01935330. S2CID 123416408.
Tarjan, Robert Endre (1975). 「線形ではないが優れた集合結合アルゴリズムの効率」. Journal of the ACM . 22 (2): 215– 225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID 11105749.
ヴァイダ、ドラゴシュ (1970)。「アルゴリズムに似た言語のコンパイラ検証」。Bulletin Mathématique de la Société des Sciences ルーマニ共和国社会主義数学。ヌーベルシリーズ。 14 (62) (4): 487–502 . JSTOR 43679758。
ウェイナー、SS (1970)。「順序再帰関数の分類」。数学ロジックとグルンドラーゲンフォルシュングのアーカイブ。13 ( 3–4 ): 136–153 .土井:10.1007/bf01973619。
Ward, Martin P. (1993年7月16日).アッカーマン関数を計算するための反復手順. CiteSeerX 10.1.1.35.9907 .
Wichmann, Brian A. (1976年3月). 「アッカーマン関数：手続き呼び出しの効率性に関する研究」. BIT Numerical Mathematics . 16 : 103–110 . CiteSeerX 10.1.1.108.4125 . doi :10.1007/BF01940783. S2CID 16993343.
Wichmann, Brian A. (1977年7月). 「手続きの呼び出し方、あるいはアッカーマン関数の再考」. BIT Numerical Mathematics . 16 (3): 103– 110. doi :10.1002/spe.4380070303. S2CID 206507320.
Wichmann, Brian A. (1982年7月). 「手続き呼び出しテスト、アッカーマン関数の最新結果」(PDF) . 2022年10月9日時点のオリジナルよりアーカイブ(PDF) 。

外部リンク

「アッカーマン関数」.数学百科事典. EMS Press . 2001 [1994].
ワイスタイン、エリック・W.「アッカーマン関数」。MathWorld。
この記事には、Paul E. Black著「アッカーマン関数」のパブリックドメイン資料が含まれています。アルゴリズムとデータ構造の辞書。NIST 。
アニメーション化されたアッカーマン関数計算機
アーロンソン、スコット(1999)「より大きな数字を言える人は誰?」
アッカーマン関数。いくつかの値の表が含まれています。
ブルベーカー、ベン（2023年12月4日）「一見簡単に思える問題が、私たちの宇宙には大きすぎる数字を生み出す」
ムナフォ、ロバート。「大きな数」。Aの定義に関するいくつかのバリエーションについて説明します。
Nivasch, Gabriel (2021年10月). 「痛みのない逆アッカーマン法」. 2007年8月21日時点のオリジナルよりアーカイブ。2023年6月18日閲覧。
Seidel, Raimund. 「逆アッカーマン関数の理解」(PDF) .
さまざまなプログラミング言語で書かれたアッカーマン関数（Rosetta Code上）
スミス、ハリー・J.「アッカーマン関数」。2009年10月26日時点のオリジナルよりアーカイブ。) 少し勉強してプログラミングをします。
Wiernik, Ady; Sharir, Micha (1988). 「非線形ダベンポート・シンツェル列の線分による平面実現」.離散幾何学と計算幾何学. 3 (1): 15– 47. doi : 10.1007/BF02187894 . MR 0918177.

[letop3-10] パラメータの順序を逆にした

[letop4-17] 「カレー風味」

[letop5-24] 各ステップで下線部のredexが書き換えられます。

[letop2-25] ここ: 左端から内側への戦略!

[letop1-26] 読みやすくするために
、S(0) は 1 と表記され、
S(S(0)) は 2 と表記され、
S(S(S(0))) は 3 と表記されます
。

[letop6-28] 再帰の最大深度とは、ある手続きの最も深い呼び出し時に存在する、その手続きの活性化の階層数を指す。Cornelius & Kirby (1975)

[letop7-29] +1回ループするDO F

[FOOTNOTEMoninHinchey200361-1] モナンとヒンシェイ、2003、p. 61.

[FOOTNOTEAckermann1928-2] アッカーマン 1928。

[3] “A(4,2)の10進展開”. kosara.net . 2000年8月27日. 2010年1月20日時点のオリジナルよりアーカイブ。

[FOOTNOTECaludeMarcusTevy1979-4] カルード、マーカス＆テヴィ 1979.

[FOOTNOTEHilbert1926185-5] ヒルベルト 1926年、185ページ。

[FOOTNOTEvan_Heijenoort1977-6] ヴァン・ヘイジェノールト 1977.

[FOOTNOTEPéter1935-7] ピーター 1935.

[FOOTNOTERobinson1948-8] ロビンソン 1948.

[FOOTNOTERitchie19651028-9] リッチー1965年、1028ページ。

[FOOTNOTEBuck1963-11] Buck 1963.

[FOOTNOTEMeeussenZantema19926-12] Meeussen & Zantema 1992、p. 6.

[FOOTNOTEMunafo1999a-13] ムナフォ 1999a.

[FOOTNOTERitchie1965-14] リッチー 1965年。

[FOOTNOTESundblad1971-15] Sundblad 1971より。

[FOOTNOTEPortoMatos1980-16] ポルト＆マトス 1980.

[FOOTNOTEOdifreddi1999298-18] オディフレディ 1999、298ページ。

[19] 「アッカーマン階層と急成長階層」。StackExchange。

[20] Pythonと同様に、オフサイドルール( INDENT ... DEDENT )に従ったインデント:
範囲( n )内の_ の場合: n += 1

[FOOTNOTEMeyerRitchie1967-21] マイヤー＆リッチー 1967年。

[FOOTNOTEGrossmanZeitman1988-22] グロスマン＆ツァイトマン 1988.

[FOOTNOTEPaulson2021-23] ポールソン 2021.

[FOOTNOTECohen198756Proposition_3.16_(see_in_proof)-27] Cohen 1987、p. 56、命題3.16（証明を参照）。

[30] グジェゴルチク階層を定義する別の関数列は、原始再帰関数を「成長クラス」に分割するために頻繁に使用されます。ただし、（または）とは添字が一致しません。 $\operatorname {E} _{n}$ $\operatorname {FGH} _{n}$ $\operatorname {A} _{n}$ $\operatorname {E} _{n}$

[FOOTNOTEPettie2002-31] ペティ 2002年。

[FOOTNOTEMatos2014-32] マトス 2014.

[FOOTNOTEBrubaker2023-33] ブルベーカー 2023.

[FOOTNOTECzerwińskiOrlikowski2022-34] チェルヴィンスキー & オルリコウスキー 2022.

[FOOTNOTELeroux2022-35] ルルー 2022年。

[FOOTNOTETarjan1975-36] タージャン 1975.

[FOOTNOTEFredmanSaks1989-37] フレッドマン＆サックス 1989.

[FOOTNOTEWiernikSharir1988-38] Wiernik & Sharir 1988.

[FOOTNOTEVaida1970-39] ヴァイダ 1970.

[FOOTNOTEWichmann1976-40] ヴィッヒマン 1976.

[FOOTNOTEWichmann1977-41] ヴィッヒマン 1977.

[FOOTNOTEWichmann1982-42] ヴィッヒマン 1982.