アッカーマン関数

アッカーマン関数
基本関数	後者関数
急増加関数	\(f_{\omega}(n)\)

アッカーマン関数 \(A(x,y)\) はヴィルヘルム・アッカーマンが定義してペーターとロビンソンが拡張した再帰関数である。現在はロビンソンの定義が有名となっている。アッカーマン数はアッカーマン関数のオリジナルの定義によって定義できる。

定義

ロビンソンの定義

次の様に定義される。

表示をデスクトップ版に切り替えて数式を表示する。

非負整数 \(x,y\) に対して, \[ A(x,y)= \begin{cases} y+1 & \text{if}\ x=0, \\ A(x-1,1) & \text{if}\ x>0, y=0, \\ A(x-1,A(x,y-1)) & \text{otherwise}. \end{cases} \]

したがって、例えば次のように計算される。

\begin{align*} A(1,2) \ &=\ A(0,A(1,1))\\ \ &=\ A(0,A(0,A(1,0)))\\ \ &=\ A(0,A(0,A(0,1)))\\ \ &=\ A(0,A(0,2))\\ \ &=\ A(0,3)\\ \ &=\ 4, \\[3px] A(2,2)\ &=\ A(1,A(2,1))\\ \ &=\ A(1,A(1,A(2,0)))\\ \ &=\ A(1,A(1,A(1,1)))\\ \ &=\ A(1,A(1,A(0,A(1,0))))\\ \ &=\ A(1,A(1,A(0,A(0,1))))\\ \ &=\ A(1,A(1,A(0,2)))\\ \ &=\ A(1, A(1, 3))\\ \ &=\ A(1, A(0, A(1, 2)))\\ \ &=\ A(1, A(0, A(0, A(1, 1))))\\ \ &=\ A(1, A(0, A(0, A(0, A(1, 0)))))\\ \ &=\ A(1, A(0, A(0, A(0, A(0, 1)))))\\ \ &=\ A(1, A(0, A(0, A(0, 2))))\\ \ &=\ A(1, A(0, A(0, 3)))\\ \ &=\ A(1, A(0, 4))\\ \ &=\ A(1, 5)\\ \ &=\ A(0, A(1, 4))\\ \ &=\ A(0, A(0, A(1, 3)))\\ \ &=\ A(0, A(0, A(0, A(1, 2))))\\ \ &=\ A(0, A(0, A(0, A(0, A(1, 1)))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, 2)))))\\ \ &=\ A(0, A(0, A(0, A(0, 3))))\\ \ &=\ A(0, A(0, A(0, 4)))\\ \ &=\ A(0, A(0, 5))\\ \ &=\ A(0, 6)\\ \ &=\ 7. \end{align*}

以下の関数\(F_n(x)\)は\(A(n,x)\)と等しくなる。 \begin{eqnarray} F_0(x) &=& x+1 \\ F_{n+1}(x) &=& F_n^{x+1}(1) \end{eqnarray}

\(x\)が小さいところでは、 \begin{align*} A(0,y) & = y+1 &&= ((y+3)+1)-3, \\ A(1,y) & = y+2 &&= 2+(y+3)-3, \\ A(2,y) & = 2y+3 &&= 2\times(y+3)-3, \\ A(3,y) & = 2^{y+3}-3 &&= 2\uparrow (y+3)-3 \end{align*} などが確かめられる。一般には、クヌースの矢印表記を用いて \[ A(x,y)=2\uparrow^{x-2}(y+3)-3 \] と書くことができる。ただし、\(x\uparrow^{-2}y=y+1\), \(\ x\uparrow^{-1}y=x+y\), \(\ x\uparrow^{0}y=x×y\) としている。 アッカーマン関数は2重再帰関数(Double recursion)であり、いかなる原始再帰関数（原始帰納関数）よりも増加速度が大きい。より正確に言えば任意の原始再帰関数はアッカーマン関数によって支配される。

オリジナルの定義

アッカーマンのオリジナルの定義は、3変数で以下のように定義された． \begin{align*} A(0,x,y)&:=x+y\\ A(n+1,x,y)&:=\underbrace{A(n,A(\cdots(A(n,x))\cdots)}_{y \text{times}} \end{align*} つまり現代的には\(A(n+2,x,y)=x\uparrow^n y\)と表すことができる．この定義は高階の原始再帰(つまり汎関数(functional)上の原始再帰)で定義されている。

フリードマンの定義

アッカーマン関数には、他にもいくつかの違った定義がある。Harvey Friedman は、アッカーマン関数を次のように定義した。

非負整数 \(x>0\), \(y\) に対して, \[ A(x,y)= \begin{cases} 1 & \text{if}\ y=0,\\ 2y & \text{if}\ x=1, y>0, \\ A(x-1,A(x,y-1)) & \text{otherwise}. \end{cases} \]

アッカーマン関数は、アッカーマン数と同じ程度の増加速度なので、関連づけられる。

アッカーマン関数は、しばしば一変数関数 \(A(n) = A(n, n)\) のことを意味する。

一変数アッカーマン関数 \(\alpha(n)\) の逆関数は、逆アッカーマン関数と言われる。アッカーマン関数は非常に増加率が高い関数であるため、逆アッカーマン関数は増加率が低い。時間的計算複雑性理論に応用される。

Goucher の定義

A.P. Goucher は、ブログの記事で以下のようなアッカーマン関数の定義を提案した。

\(f_1(n)=n+2\)

\(f_{m+1}(n) = f_m^n(2)\)

\(A(n) = f_n(n)\)

またこの投稿では次のような問題からアッカーマン関数の変種を考え出すことが出来る:

箱がいくつか並んでいて、コインが1枚づつ入っている。ここで、この箱に次のような操作を施す:

• 一つの箱から1枚のコインを取り出し、その右の箱に2枚コインを入れる。
• 一つの箱から1枚のコインを取り出し、その右の箱に入っているコインとそのさらに右の箱のコインの枚数を入れ替える。

右端の箱を除き箱にコインが入っていないという状況を考える。nを箱の個数とし、f(n)を右端のコインの個数の最大値とする。最初のほうの値は、 \[ \begin{array} \\ f(1) = 1 \\ f(2) = 3 \\ f(3) = 7 \\ f(4) = 28 \\ \end{array} \] である。

ちなみに、2010年国際数学オリンピックの第五問は、f(6)>2010^20102010の証明だった。

プログラム

以下はアッカーマン関数の計算を実行するプログラムである：

• 巨大数：アッカーマン関数のC++実装
• アッカーマン関数計算過程表示プログラム
• Aycabta, Ackermann, github repository, 2012.
• ふぃっしゅ, Ackermann (Python), github repository, 2018
• koteitan, ack, github repository, 2022.
• Mitsuki1729, アッカーマン関数 scratch巨大数選手権コンテスト, scratch.

拡張

アッカーマン関数を多変数に拡張した多変数アッカーマン関数により、さらに増加率の高い関数を定義できる。

関連項目

• アッカーマン数
• 多重帰納関数
• 多変数アッカーマン関数
• 2重リストアッカーマン関数
• 多重リストアッカーマン関数