アッカーマン関数

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

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

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

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

また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを(再帰のない手続き型の)プログラミング言語の言葉で言えば、whileループを使えばアッカーマン関数をプログラミングできるが、whileを使わずにforループだけでは実現不能だということである。

なお、アッカーマン関数のグラフは原始再帰的である。

歴史

1920年代後半、数学者ダフィット・ヒルベルトの教導を受けていた学生だったガブリエル・スーダンとヴィルヘルム・アッカーマンは、計算の基礎を研究していた。

スーダンとアッカーマンの双方が全域計算可能関数（いくつかの参考文献では単純に "再帰的"と呼ばれる）でありながら原始再帰的でない関数の発見に功績が有ったと信じられている。

スーダンがあまり知られていないスーダン関数を公表し独立した後、1928年アッカーマンは自分の生み出した関数 $\varphi \,\!$（ギリシャ文字のファイ）を公表する。その関数は3つの引数を必要とし $\varphi (m,n,p)\,\!$ の様に表記された。

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

多くの数学者に愛用される事になった2変数形式のアッカーマン関数は、ラファエル・M・ロビンソンとロザ・ペーターに開発された。

概念

$a+b,a\cdot b,a^{b},\ldots$ という列を想定すると、その全ての項は b 個の a で演算を b − 1 回繰り返すことで、次項に変換される。（例えば第一項 $a+b$ で行われた加算を b 個の a の b − 1 個間全てで行うと、第二項 $a\cdot b$ と等価になる。）

例： 上記の列に $a=2,b=4$ を代入すると、6, 8, 16, 65536, $2^{2^{.^{.^{.^{2}}}}}$(65536階立の指数タワー)　, ... という数列となる。第5項目の数はすでに、宇宙のすべての原子の推定数よりもはるかに大きい。

アッカーマン関数の背後には、この考え方があると思うべきである。オリジナルのアッカーマン関数 $\varphi$ は、以下のリストを満たす関数である:

$\varphi (a,b,0)=a+b\,$

$\varphi (a,b,1)=a\cdot b$

$\varphi (a,b,2)=a^{b}\,$

$\ldots$

第4行目からは、一般的な演算子では書き表せなくなり、ハイパー演算子など高度で専門的な表記法を必要とする。

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

アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 (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	$2n+3=2\times (n+3)-3$
3	5	13	29	61	125	$2^{n+3}-3$
4	13	65533	265536 − 3	${2^{2^{65536}}}-3$	A(3, A(4, 3)) = 22265536 − 3	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\text{ + 3 twos}}\end{matrix}}$
5	65533	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\65536{\text{ twos}}\end{matrix}}$	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	$\operatorname {A} (4,\operatorname {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))	$\operatorname {A} (5,\operatorname {A} (6,n-1))$

再帰的な参照で表示している値は非常に大きいが、クヌースの矢印表記、コンウェイのチェーン表記、ハイパー演算子等を使えば

$\operatorname {Ack} (m,n)$

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

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

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

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

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

以下は、上記のテーブルと同じものであるが、パターンを分かりやすくするため、値を関数定義の表現に置き換えている。

A(m, n) の値

m\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,A(1,1))	A(0,A(1,2))	A(0,A(1,3))	$n+2=2+(n+3)-3$
2	A(1,1)	A(1,A(2,0))	A(1,A(2,1))	A(1,A(2,2))	A(1,A(2,3))	$2n+3=2\times (n+3)-3$
3	A(2,1)	A(2,A(3,0))	A(2,A(3,1))	A(2,A(3,2))	A(2,A(3,3))	$2^{n+3}-3$
4	A(3,1)	A(3,A(4,0))	A(3,A(4,1))	A(3,A(4,2))	A(3,A(4,3))	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\text{ + 3 twos}}\end{matrix}}$
5	A(4,1)	A(4,A(5,0))	A(4,A(5,1))	A(4,A(5,2))	A(4,A(5,3))	$\operatorname {A} (4,\operatorname {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))	$\operatorname {A} (5,\operatorname {A} (6,n-1))$

関連項目

• 巨大数
• ヴィルヘルム・アッカーマン
• 竹内関数
• グッドスタイン関数
• 素集合データ構造
• ヴィルヘルム・アッカーマン
• 二重再帰法

参考文献

• 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)

外部リンク

• Weisstein, Eric W. "Ackermann Function." From MathWorld. （英語）