アッカーマン関数

アッカーマン関数（アッカーマンかんすう、テンプレート:Lang-en-short、テンプレート:Lang-de-short）とは、非負整数 m と n に対し、

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

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

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

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

歴史

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

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

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

2変数形式に単純化されたアッカーマン関数は、1935年テンプレート:Ill2によって開発された。

概念

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

$\begin{array}{cc}\phi (a,b,0)& =a+b\\ \phi (a,0,n+1)& =\{\begin{array}{cc}n& (\text{if}n=0,1)\\ a& (\text{otherwise})\end{array}\\ \phi (a,b+1,n+1)& =\phi (a,\phi (a,b,n+1),n)\end{array}$

この関数において、$\phi (a,b,n+1)$ は $\phi (a,\mathrm{\_},n)$ を テンプレート:Mvar 回繰り返すことによって定義されていることがわかる。すなわち、

$\begin{array}{cc}\phi (a,b,0)& =a+b\\ \phi (a,b,1)& =0+\underset{b\text{times}}{\underbrace{a+\cdots +a}}=a\cdot b\\ \phi (a,b,2)& =1\cdot \underset{b\text{times}}{\underbrace{a\cdot \cdots \cdot a}}=a^b\\ \phi (a,b,3)& =\underset{(b+1)\text{times}}{\underbrace{a^{a^{{\cdot }^{{\cdot }^{{\cdot }^a}}}}}}\\ & ⋮\end{array}$

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

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

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

A(m,n) の値

mテンプレート:Backslashn	0	1	2	3	4	n
0	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
1	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
2	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
3	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
︙	テンプレート:Math	︙	︙	︙	︙	︙

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

A(m,n) の値

mテンプレート:Backslashn	0	1	2	3	4	n
0	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
1	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math
2	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	$2n+3=2\times (n+3)-3$
3	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	テンプレート:Math	$2^{n+3}-3$
4	テンプレート:Math	テンプレート:Math	$2^{65536}-3$	$2^{2^{65536}}-3$	$2^{2^{2^{65536}}}-3$	$\begin{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\\ n\text{ + 3 twos}\end{array}$
5	テンプレート:Math	$\begin{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\\ 65536\text{ twos}\end{array}$	$A(4,A(5,1))$	$A(4,A(5,2))$	$A(4,A(5,3))$	$A(4,A(5,n-1))$

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

$A(m,n)$

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

$=(2\to (n+3)\to (m-2))-3$

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

$=\mathrm{h}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{r}𝑚(2,n+3)-3$

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

十分にテンプレート:Mvarの値を大きくしたとき、アッカーマン関数の値は急増加関数で$A(x,a)\approx f_{\omega }(x)$（$a$ は定数）と近似できる。

逆アッカーマン関数

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

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

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

参考文献

• Y. Sundblad: The Ackermann Function. A theoretical, computational, and formulamanipulative study. BIT 11, 107–119 (1971)
• 竹内外史『数学基礎論の世界　ロジックの雑記帳から』日本評論社、1972年、ISBN 4-535-78126-5
• マイケル・シプサー著、『計算理論の基礎』太田和夫・田中圭介 監訳, 共立出版。原著： "Introduction to the Theory of Computation" (Michael Sipser, Thomson Course Technology)

関連項目

• ヴィルヘルム・アッカーマン
• テンプレート:仮リンク
• 素集合データ構造
• 二重再帰法
• 巨大数
• 急増加関数
• ハイパー演算子
• クヌースの矢印表記
• コンウェイのチェーン表記
• 配列表記

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:MathWorld