アッカーマン関数

アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、

${\displaystyle A(m,n)={\begin{cases}n+1,&{\text{ if }}m=0\\A(m-1,1),&{\text{ if }}n=0\\A(m-1,A(m,n-1)),&{\text{ otherwise}}\\\end{cases}}}$

によって定義される関数のことである^[1]。

与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。

また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。

歴史

1920年代後半、数学者ダフィット・ヒルベルトの教導を受けていた学生だったガブリエル・スーダン（英語版）とヴィルヘルム・アッカーマンは、計算の基礎を研究していた。ヒルベルトは、すべての計算可能関数が 原始再帰的であると仮定していた^[要出典]。簡単に言えば、これは、コンピューターで計算できる各関数をいくつかの非常に単純なルールからまとめて、計算の期間を事前に推定できることを意味する。実際にこれは人々が利用するほとんどの関数に適用出来るが、2人の研究はそれを覆した。

1927年に、スーダンはスーダン関数を発表した。それとは独立に、1928年アッカーマンは自分の生み出した関数 ${\displaystyle \varphi \,\!}$ を公表する。その関数は3つの引数を必要とし ${\displaystyle \varphi (m,n,p)\,\!}$ の様に表記された^[2]。スーダンとアッカーマンの双方が全域計算可能関数（いくつかの参考文献では単純に "再帰的"と呼ばれる）でありながら原始再帰的でない関数の発見に功績が有ったと信じられている^[3]。

ヒルベルトはÜber das Unendliche^[4]の中でアッカーマン関数が原始再帰的では無いと仮定したが、この仮説は彼の個人秘書となっていたアッカーマンによって実際に証明され、ヒルベルトの執筆した実数の論文上に掲載された^[2][5]。

2変数形式に単純化されたアッカーマン関数は、1935年ペーテル・ロージャ（英語版）によって開発された^[6]。

概念

アッカーマンが1928年に発表した3変数の関数は次のような定義である^[2]：

${\displaystyle {\begin{aligned}\varphi (a,b,0)&=a+b\\\varphi (a,0,n+1)&={\begin{cases}n&({\textrm {if}}\ n=0,1)\\a&({\textrm {otherwise}})\\\end{cases}}\\\varphi (a,b+1,n+1)&=\varphi (a,\varphi (a,b,n+1),n)\end{aligned}}}$

この関数において、${\displaystyle \varphi (a,b,n+1)}$ は ${\displaystyle \varphi (a,\_,n)}$ を b 回繰り返すことによって定義されていることがわかる。すなわち、

${\displaystyle {\begin{aligned}\varphi (a,b,0)&=a+b\\\varphi (a,b,1)&=0+\underbrace {a+\cdots +a} _{b\;{\textrm {times}}}=a\cdot b\\\varphi (a,b,2)&=1\cdot \underbrace {a\cdot \cdots \cdot a} _{b\;{\textrm {times}}}=a^{b}\\\varphi (a,b,3)&=\underbrace {a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}} _{(b+1)\;{\textrm {times}}}\\&\;\;\vdots \end{aligned}}}$

となるように定義されている。

アッカーマン関数の値の表

アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を1から順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 (n = 1) の数値を取る。

A(m,n) の値

m\n	0	1	2	3	4	n
0	1	2	3	4	5	n+1
1	A(0, 1)	A(0, A(1, 0))	A(0, A(1, 1))	A(0, A(1, 2))	A(0, A(1, 3))	A(0, A(1, n-1))
2	A(1, 1)	A(1, A(2, 0))	A(1, A(2, 1))	A(1, A(2, 2))	A(1, A(2, 3))	A(1, A(2, n-1))
3	A(2, 1)	A(2, A(3, 0))	A(2, A(3, 1))	A(2, A(3, 2))	A(2, A(3, 3))	A(2, A(3, n-1))
︙	︙	︙	︙	︙	︙	︙

計算できる範囲で具体的な数値に置き換えていくと、表は次のようになる。

A(m,n) の値

m\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	${\displaystyle 2n+3=2\times (n+3)-3}$
3	5	13	29	61	125	${\displaystyle 2^{n+3}-3}$
4	13	65533	${\displaystyle 2^{65536}-3}$	${\displaystyle {2^{2^{65536}}}-3}$	${\displaystyle 2^{2^{2^{65536}}}-3}$	${\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\text{ + 3 twos}}\end{matrix}}}$
5	65533	${\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\65536{\text{ twos}}\end{matrix}}}$	${\displaystyle A(4,A(5,1))}$	${\displaystyle A(4,A(5,2))}$	${\displaystyle A(4,A(5,3))}$	${\displaystyle A(4,A(5,n-1))}$

一般の値は非常に大きいが、クヌースの矢印表記、コンウェイのチェーン表記、ハイパー演算子等を使えば

${\displaystyle A(m,n)}$

${\displaystyle =\left(2\uparrow ^{m-2}\left(n+3\right)\right)-3}$

${\displaystyle =\left(2\rightarrow \left(n+3\right)\rightarrow \left(m-2\right)\right)-3}$

${\displaystyle =\operatorname {hyper} (2,m,n+3)-3}$

${\displaystyle =\operatorname {hyper{\mathit {m}}} (2,n+3)-3}$

と簡潔に表す事が出来る。

十分にxの値を大きくしたとき、アッカーマン関数の値は急増加関数のひとつであるウェイナー階層で${\displaystyle A(x,a)\thickapprox f_{\omega }(x)}$（${\displaystyle a}$ は定数）と近似できる。

逆アッカーマン関数

自然数nに対して${\displaystyle A(m-1,m-1)<n\leq A(m,m)}$を満たすようなmを取り、${\displaystyle \alpha (n)=m}$として関数αを定義する。この関数を逆アッカーマン関数という。このとき定義から逆アッカーマン関数は全域かつ上界を持たないが、その値は非常にゆっくりと大きくなる。

ロバート・タージャンの1975年の論文において提唱された素集合データ構造 (Union-Find) の探索および結合アルゴリズムについて、その計算量が ${\displaystyle O(\alpha (n))}$ で見積もられた^[7]。

逆アッカーマン関数は原始再帰関数である。