アッカーマン関数

計算可能性理論において、ヴィルヘルム・アッカーマンにちなんで名付けられたアッカーマン関数は、原始再帰関数ではない全計算可能関数の最も単純な例^[¹^]であり、最も初期に発見された例の一つである。すべての原始再帰関数は全計算可能関数であるが、アッカーマン関数は、すべての全計算可能関数が原始再帰関数であるとは限らないことを示している。これは基本的に、一連の原始再帰関数を対角化することによって構成される。 $f_{1},f_{2},\dots$ グレゴルチク階層から選択されます。これにより、アッカーマン関数が最初の極限点になります。 $f_{\omega }$ 急速に拡大する階層構造の。

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

歴史

1920年代後半、ダヴィッド・ヒルベルトの弟子であった数学者のガブリエル・スーダンとヴィルヘルム・アッカーマンは、^{計算の基礎を研究していた。スーダンとアッカーマンはともに、原始再帰関数ではない全計算可能関数（一部の文献では単に「再帰的」と呼ばれる）を発見したとされている[} 4 ] 。^スーダンはあまり知られてい^ないスーダン関数を発表し、その後まもなく、1928年にアッカーマンが独立して自身の関数を発表した。 $\varphi$ （ギリシャ語の文字φに由来）。アッカーマンの3引数関数、 $\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 ]}^[⁶^]においてであった。

Rózsa Péter ^{[ 7 ]}と Raphael Robinson ^{[ 8 ]}は後に、ほぼすべての著者が好むようになった 2 変数バージョンのアッカーマン関数を開発しました。

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

1963年、R. クレイトン・バックは直感的な2変数^{[ n 1 ]の}変種に基づいて $\operatorname {F}$ ハイパーオペレーションシーケンスについて：^{[ 10 ]}^{[ 11 ]}

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

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

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

意味

定義: m項関数として

アッカーマンのオリジナルの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 引数バージョンのさまざまなもののうち、ペーターとロビンソンによって開発されたもの（ほとんどの著者によって「アッカーマン関数」と呼ばれている）は、非負の整数に対して定義されています。 $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}}$

または、クヌースの上向き矢印記法（整数インデックスに拡張）で記述すると、 $\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項関数として

定義する $f^{n}$ 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)$ 。

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

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

計算

ループプログラムによる計算

機能 $\operatorname {A} _{i}$ 関数の（有限レベルの）急成長階層（FGH）に適合する^{[ 16 ]}

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

固定の場合 $k$ 関数 $\operatorname {FGH} _{k}(n)$ ネスト深度のLOOP プログラムで計算できます $k$ : ^{[ 18 ]}

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

機能 $\operatorname {A} _{k}(n)$ LOOP-k プログラムによって計算することもできます。^{[ 19 ]}（プログラム（回路図）はここには記載されていません。）

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

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 ]です}

計算する $\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$ 、

備考

左端内側戦略は、Rosetta Code上の 225 のプログラミング言語で実装されています。
すべての人にとって $m,n$ 計算 $A(m,n)$ 必要なのは $(A(m,n)+1)^{m}$ ステップ。^{[ 22 ]}
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)$ 空間。

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

反復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 と「同じ」とみなされます)。たとえば、削減は $A(2,1)$ 14ステップで収束します: 6 × r1、3 × r2、5 × r3。 $A_{2}(1)$ 同じ 14 ステップ (6 × r4、3 × r5、5 × r6/r7) で収束します。TRS の違いは、縮小規則が適用される順序です。
いつ $A_{i}(n)$ ルール{r4, r5, r6}に従って計算され、スタックの最大長は以下になります。 $2\times A(i,n)$ ルールr6の代わりに削減ルールr7を使用すると、スタックの最大長は $2(i+2)$ スタックの長さは再帰の深さを反映しています。ルール {r4, r5, r7} に従った削減では再帰の最大深さが小さくなるため、^{[ n 6 ]}この計算はその点でより効率的です。

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

サンドブラッド（1971）やポルト＆マトス（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}}$

バック関数 $\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$

一致する等式は次のとおりです。

削減ルールを用いた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}}$ 備考

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

膨大な数

計算方法を説明するために $A(4,3)$ 結果は多くのステップと多数の結果になります: ^{[ n 5 ]}

${\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)$ 必ず終了します。ただし、再帰は制限されています。なぜなら、各再帰適用では、 $m$ 減少する、または $m$ 同じままで $n$ 減少します。 $n$ ゼロに達する、 $m$ 減少するので $m$ 最終的にはゼロにも達する。（より技術的に表現すると、いずれの場合もペアは $(m,n)$ ペアの辞書式順序は減少します。これは整列順序であり、単一の非負整数の順序と同じです。つまり、順序を無限に連続して下げることはできません。）しかし、 $m$ 減少する量に上限はない $n$ 増加する可能性があり、多くの場合、大幅に増加する。
mの値が1、2、3のような小さい場合、アッカーマン関数はnに対して比較的ゆっくりと増加します（せいぜい指数関数的に）。 $m\geq 4$ しかし、それははるかに速く成長します。 $A(4,2)$ 約 2.00353 × 10^{19 728}、そしてその十進展開 $A(4,3)$ は、一般的な尺度では非常に大きく、約 2.12004 × 10 ^{6.03123 × 10です。^{19 727}}。
興味深い点は、このプログラムが使用する算術演算は1の加算のみであるということです。その急速な処理能力の向上は、ネストされた再帰処理のみに基づいています。これは、実行時間が少なくとも出力に比例し、したがって非常に長くなることを意味します。実際には、ほとんどの場合、実行時間は出力よりもはるかに長くなります（上記参照）。
引数が1つのバージョン $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)$

どこ $\operatorname {FGH} _{k}^{n}$ 意味する $n$ -fold反復 $\operatorname {FGH} _{k}$ 入力時 $n$ ^{[ 23 ]}この階層構造は、増加に伴い厳密に速く成長する。 $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)は 1 のオーダーであるため、任意の実用的な入力サイズnに対してα ( n ) は 5 未満です。 $2^{2^{2^{2^{16}}}}$ 。

この逆関数は、非連結集合データ構造や最小全域木を求めるシャゼルのアルゴリズムなど、いくつかのアルゴリズムの時間計算量に現れます。これらの設定では、アッカーマンの元の関数や他の変種が使用されることもありますが、いずれも同様に高い割合で増加します。特に、いくつかの修正関数は、−3や同様の項を削除することで式を簡略化します。

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

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

This function arises in more precise analyses of the algorithms mentioned above, and gives a more refined time bound. In the disjoint-set data structure, m represents the number of operations while n represents the number of elements; in the minimum spanning tree algorithm, m represents the number of edges while n represents the number of vertices. Several slightly different definitions of α(m, n) exist; for example, log₂n is sometimes replaced by n, and the floor function is sometimes replaced by a ceiling.

Other studies might define an inverse function of one where m is set to a constant, such that the inverse applies to a particular row.^[24]

The inverse of the Ackermann function is primitive recursive, since it is graph primitive recursive, and it is upper bounded by a primitive recursive function.^[25]

Usage

In computational complexity

The Ackermann function appears in the time complexity of some algorithms,^[26] such as vector addition systems^[27] and Petri net reachability, thus showing they are computationally infeasible for large instances.^[28]

The inverse of the Ackermann function appears in some time complexity results. For instance, the disjoint-set data structure takes amortized time per operation proportional to the inverse Ackermann function,^[29] and cannot be made faster within the cell-probe model of computational complexity.^[30]

In discrete geometry

Certain problems in discrete geometry related to Davenport–Schinzel sequences have complexity bounds in which the inverse Ackermann function $\alpha (n)$ appears. For instance, for $n$ line segments in the plane, the unbounded face of the arrangement of the segments has complexity $O(n\alpha (n))$ , and some systems of $n$ line segments have an unbounded face of complexity $\Omega (n\alpha (n))$ .^[31]

As a benchmark

The Ackermann function, due to its definition in terms of extremely deep recursion, can be used as a benchmark of a compiler's ability to optimize recursion. The first published use of Ackermann's function in this way was in 1970 by Dragoș Vaida^[32] and, almost simultaneously, in 1971, by Yngve Sundblad.^[14]

Sundblad's seminal paper was taken up by Brian Wichmann (co-author of the Whetstone benchmark) in a trilogy of papers written between 1975 and 1982.^[33]^[34]^[35]

Notes

↑with parameter order reversed
↑'curried'
↑In each step the underlined redex is rewritten.
1 2here: leftmost-innermost strategy!
1 2 3 4For better readabilityS(0) is notated as 1,S(S(0)) is notated as 2,S(S(S(0))) is notated as 3,etc...
↑The maximum depth of recursion refers to the number of levels of activation of a procedure that exist during the deepest call of the procedure. Cornelius & Kirby (1975)
↑LOOP n+1 TIMES DO F

References

↑Monin & Hinchey 2003, p. 61.
1 2Ackermann 1928.
↑"Decimal expansion of A(4,2)". kosara.net. 27 August 2000. Archived from the original on 20 January 2010.
↑Calude, Marcus & Tevy 1979.
↑Hilbert 1926, p. 185.
↑van Heijenoort 1977.
↑Péter 1935.
↑Robinson 1948.
↑Ritchie 1965, p. 1028.
1 2 3Buck 1963.
↑Meeussen & Zantema 1992, p. 6.
↑Munafo 1999a.
↑Ritchie 1965.
1 2Sundblad 1971.
↑Porto & Matos 1980.
↑Odifreddi 1999, p. 298.
↑"The Ackermann hierarchy vs. the fast growing hierarchy". StackExchange.
↑
Indentation according to the off-side rule (INDENT ... DEDENT), like in Python:
```
for_inrange(n):n+=1
```
↑Meyer & Ritchie 1967.
↑Grossman & Zeitman 1988.
↑Paulson 2021.
↑Cohen 1987, p. 56, Proposition 3.16 (see in proof).
↑Another sequence of functions, $\operatorname {E} _{n}$ , defining the Grzegorczyk hierarchy, is frequently used to partition the primitive recursive functions into "growth classes". However, $\operatorname {FGH} _{n}$ (or $\operatorname {A} _{n}$ ) and $\operatorname {E} _{n}$ do not align in their indexing.
↑Pettie 2002.
↑Matos 2014.
↑Brubaker 2023.
↑Czerwiński & Orlikowski 2022.
↑Leroux 2022.
↑Tarjan 1975.
↑Fredman & Saks 1989.
↑Wiernik & Sharir 1988.
↑Vaida 1970.
↑Wichmann 1976.
↑Wichmann 1977.
↑Wichmann 1982.

Bibliography

Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen"[On the Hilbertian construction of the real numbers]. Mathematische Annalen (in German). 99: 118–133. doi:10.1007/BF01459088. S2CID 123431274.
Buck, R. C. (1963). "Mathematical Induction and Recursive Definitions". American Mathematical Monthly. 70 (2): 128–135. doi:10.2307/2312881. JSTOR 2312881.
Calude, Cristian; Marcus, Solomon; Tevy, Ionel (November 1979). "The first example of a recursive function which is not primitive recursive". Historia Math.6 (4): 380–84. doi:10.1016/0315-0860(79)90024-7.
Cohen, Daniel E. (January 1987). Computability and logic. Halsted Press. ISBN 9780745800349.
Cornelius, B. J.; Kirby, G. H. (1975). "Depth of recursion and the Ackermann function". BIT Numerical Mathematics. 15 (2): 144–150. doi:10.1007/BF01932687. S2CID 120532578.
Czerwiński, Wojciech; Orlikowski, Łukasz (7 February 2022). Reachability in Vector Addition Systems is Ackermann-complete. 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. (May 1989). "The cell probe complexity of dynamic data structures". Proceedings of the twenty-first annual ACM symposium on Theory of computing – STOC '89. pp. 345–354. doi:10.1145/73007.73040. ISBN 0897913078. S2CID 13470414.
Grossman, Jerrold W.; Zeitman, R. Suzanne (May 1988). "An inherently iterative computation of ackermann's function". Theoretical Computer Science. 57 (2–3): 327–330. doi:10.1016/0304-3975(88)90046-1.
van Heijenoort, Jean (1977) [reprinted with corrections, first published in 1967]. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press.
Hilbert, David (1926). "Über das Unendliche" [On the infinite]. Mathematische Annalen (in German). 95: 161–190. doi:10.1007/BF01206605. S2CID 121888793.
Leroux, Jérôme (7 February 2022). The Reachability Problem for Petri Nets is Not Primitive Recursive. Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science. arXiv:2104.12695. doi:10.1109/FOCS52979.2021.00121.
Löb, M. H.; Wainer, S. S. (1970). "Hierarchies of number-theoretic functions. I.". Archiv für mathematische Logik und Grundlagenforschung. 13 (1–2): 39–51. doi:10.1007/BF01967649.
Matos, Armando B (7 May 2014). "The inverse of the Ackermann function is primitive recursive"(PDF). Archived(PDF) from the original on 9 October 2022.
Meeussen, V. C. S.; Zantema, H. (1992). Derivation lengths in term rewriting from interpretations in the naturals(PDF) (Report). University of Utrecht Department of Computer Science. ISSN 0924-3275. Archived(PDF) from the original on 9 October 2022.
Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). "The complexity of loop programs". Proceedings of the 1967 22nd national conference. ACM '67: Proceedings of the 1967 22nd national conference. pp. 465–469. doi:10.1145/800196.806014.
Monin, Jean-Francois; Hinchey, M. G. (2003). Understanding Formal Methods. Springer. p. 61. ISBN 9781852332471.
Munafo, Robert (1999a). "Versions of Ackermann's Function". Large Numbers at MROB. Retrieved 6 November 2021.
Munafo, Robert (1999b). "Inventing New Operators and Functions". Large Numbers at MROB. Retrieved 6 November 2021.
Odifreddi, Piergiorgio (1999). Classical recursion theory. Vol. II. Studies in Logic and the Foundations of Mathematics. Vol. 143. Amsterdam: North-Holland. ISBN 978-0-444-50205-6. MR 1718169.
Paulson, Lawrence C. (2021). "Ackermann's Function in Iterative Form: A Proof Assistant Experiment". Retrieved 19 October 2021.
Péter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen" [Construction of non-recursive functions]. Mathematische Annalen (in German). 111: 42–60. doi:10.1007/BF01472200. S2CID 121107217.
Pettie, S. (2002). "An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. pp. 155–163. doi:10.1109/SFCS.2002.1181892. ISBN 0-7695-1822-2. S2CID 8636108.
Porto, António; Matos, Armando B. (1 September 1980). "Ackermann and the superpowers"(PDF). ACM SIGACT News. 12 (3): 90–95. doi:10.1145/1008861.1008872. S2CID 29780652. Archived(PDF) from the original on 9 October 2022. Original version 1980, published in ACM SIGACT News, modified on 20 October 2012 and 23 January 2016 (working paper)
Ritchie, Robert Wells (November 1965). "Classes of recursive functions based on Ackermann's function". Pacific Journal of Mathematics. 15 (3): 1027–1044. doi:10.2140/pjm.1965.15.1027.
Robinson, Raphael Mitchel (1948). "Recursion and Double Recursion". Bulletin of the American Mathematical Society. 54 (10): 987–93. doi:10.1090/S0002-9904-1948-09121-2.
Sundblad, Yngve (March 1971). "The Ackermann function. A theoretical, computational, and formula manipulative study". BIT Numerical Mathematics. 11 (1): 107–119. doi:10.1007/BF01935330. S2CID 123416408.
Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.
Vaida, Dragoș (1970). "Compiler Validation for an Algol-like Language". Bulletin Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie. Nouvelle série. 14 (62) (4): 487–502. JSTOR 43679758.
Wainer, S. S. (1970). "A classification of the ordinal recursive functions". Archiv für mathematische Logik und Grundlagenforschung. 13 (3–4): 136–153. doi:10.1007/bf01973619.
Ward, Martin P. (16 July 1993). Iterative Procedures for Computing Ackerman's Function. CiteSeerX 10.1.1.35.9907.
Wichmann, Brian A. (March 1976). "Ackermann's function: A study in the efficiency of calling procedures". BIT Numerical Mathematics. 16: 103–110. CiteSeerX 10.1.1.108.4125. doi:10.1007/BF01940783. S2CID 16993343.
Wichmann, Brian A. (July 1977). "How to call procedures, or second thoughts on Ackermann's function". BIT Numerical Mathematics. 16 (3): 103–110. doi:10.1002/spe.4380070303. S2CID 206507320.
Wichmann, Brian A. (July 1982). "Latest results from the procedure calling test, Ackermann's function"(PDF). Archived(PDF) from the original on 9 October 2022.

External links

"Ackermann function". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
Weisstein, Eric W."Ackermann function". MathWorld.
This article incorporates public domain material from Paul E. Black. "Ackermann's function". Dictionary of Algorithms and Data Structures. NIST.
An animated Ackermann function calculator
Aaronson, Scott (1999). "Who Can Name the Bigger Number?".
Ackermann functions. Includes a table of some values.
Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe".
Munafo, Robert. "Large Numbers". describes several variations on the definition of A.
Nivasch, Gabriel (October 2021). "Inverse Ackermann without pain". Archived from the original on 21 August 2007. Retrieved 18 June 2023.
Seidel, Raimund. "Understanding the inverse Ackermann function"(PDF).
The Ackermann function written in different programming languages, (on Rosetta Code)
Smith, Harry J. "Ackermann's Function". Archived from the original on 26 October 2009.) Some study and programming.
Wiernik, Ady; Sharir, Micha (1988). "非線形Davenport–Schinzel数列のセグメントによる平面実現" . Discrete & Computational Geometry . 3 (1): 15– 47. doi : 10.1007/BF02187894 . MR 0918177 .

[letop3-10] with parameter order reversed

[letop4-17] 'curried'

[letop5-24] In each step the underlined redex is rewritten.

[letop2-25] 1 2here: leftmost-innermost strategy!

[letop1-26] 1 2 3 4For better readabilityS(0) is notated as 1,S(S(0)) is notated as 2,S(S(S(0))) is notated as 3,etc...

[letop6-28] The maximum depth of recursion refers to the number of levels of activation of a procedure that exist during the deepest call of the procedure. Cornelius & Kirby (1975)

[letop7-29] LOOP n+1 TIMES DO F

[FOOTNOTEMoninHinchey200361-1] Monin & Hinchey 2003, p. 61.

[FOOTNOTEAckermann1928-2] 1 2Ackermann 1928.

[3] "Decimal expansion of A(4,2)". kosara.net. 27 August 2000. Archived from the original on 20 January 2010.

[FOOTNOTECaludeMarcusTevy1979-4] Calude, Marcus & Tevy 1979.

[FOOTNOTEHilbert1926185-5] Hilbert 1926, p. 185.

[FOOTNOTEvan_Heijenoort1977-6] van Heijenoort 1977.

[FOOTNOTEPéter1935-7] Péter 1935.

[FOOTNOTERobinson1948-8] Robinson 1948.

[FOOTNOTERitchie19651028-9] Ritchie 1965, p. 1028.

[FOOTNOTEBuck1963-11] 1 2 3Buck 1963.

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

[FOOTNOTEMunafo1999a-13] Munafo 1999a.

[FOOTNOTERitchie1965-14] Ritchie 1965.

[FOOTNOTESundblad1971-15] 1 2Sundblad 1971.

[FOOTNOTEPortoMatos1980-16] Porto & Matos 1980.

[FOOTNOTEOdifreddi1999298-18] Odifreddi 1999, p. 298.

[19] "The Ackermann hierarchy vs. the fast growing hierarchy". StackExchange.

[20] Indentation according to the off-side rule (INDENT ... DEDENT), like in Python:
for_inrange(n):n+=1

[FOOTNOTEMeyerRitchie1967-21] Meyer & Ritchie 1967.

[FOOTNOTEGrossmanZeitman1988-22] Grossman & Zeitman 1988.

[FOOTNOTEPaulson2021-23] Paulson 2021.

[FOOTNOTECohen198756Proposition_3.16_(see_in_proof)-27] Cohen 1987, p. 56, Proposition 3.16 (see in proof).

[30] Another sequence of functions, $\operatorname {E} _{n}$ , defining the Grzegorczyk hierarchy, is frequently used to partition the primitive recursive functions into "growth classes". However, $\operatorname {FGH} _{n}$ (or $\operatorname {A} _{n}$ ) and $\operatorname {E} _{n}$ do not align in their indexing.

[FOOTNOTEPettie2002-31] Pettie 2002.

[FOOTNOTEMatos2014-32] Matos 2014.

[FOOTNOTEBrubaker2023-33] Brubaker 2023.

[FOOTNOTECzerwińskiOrlikowski2022-34] Czerwiński & Orlikowski 2022.

[FOOTNOTELeroux2022-35] Leroux 2022.

[FOOTNOTETarjan1975-36] Tarjan 1975.

[FOOTNOTEFredmanSaks1989-37] Fredman & Saks 1989.

[FOOTNOTEWiernikSharir1988-38] Wiernik & Sharir 1988.

[FOOTNOTEVaida1970-39] Vaida 1970.

[FOOTNOTEWichmann1976-40] Wichmann 1976.

[FOOTNOTEWichmann1977-41] Wichmann 1977.

[FOOTNOTEWichmann1982-42] Wichmann 1982.

[

[ 2 ]

[ 3 ]

計算の基礎を研究していた。スーダンとアッカーマンはともに、原始再帰関数ではない全計算可能関数（一部の文献では単に「再帰的」と呼ばれる）を発見したとされている[

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[ n 1 ]の

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ n 2 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ n 3 ]です

[ n 4 ]

[ 22 ]

[ n 6 ]

[ n 7 ]

[ n 5 ]

[ 23 ]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

歴史

意味