アッカーマン関数

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

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

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

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

概念

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

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

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

${\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$	$2n+3=2\times (n+3)-3$
3	$5$	$13$	$29$	$61$	$125$	$2^{n+3}-3$
4	$13$	$65533$	$2^{65536}-3$	${2^{2^{65536}}}-3$	$2^{2^{2^{65536}}}-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))$	$A(4,A(5,n-1))$

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

A(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{\mathit {m}}} (2,n+3)-3

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

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

逆アッカーマン関数

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

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

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

脚注

^ 日本数学会編『岩波数学辞典第4版』（1版）岩波書店、2007年、334頁。ISBN 978-4000803090。
^ ^a ^b ^c Wilhelm Ackermann (1928). “Zum Hilbertschen Aufbau der reellen Zahlen”. Mathematische Annalen 99: 118–133. doi:10.1007/BF01459088.
^ Cristian Calude, Solomon Marcus（英語版） and Ionel Tevy (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.
^ Hilbert, David (1926-12-01). “Über das Unendliche” (ドイツ語). Mathematische Annalen 95 (1): 161–190. doi:10.1007/BF01206605. ISSN 1432-1807. https://doi.org/10.1007/BF01206605.
^ von Heijenoort. From Frege To Godel Archived May 4, 2008, at the Wayback Machine., 1967.
^ Raphael M. Robinson (1948). “Recursion and Double Recursion”. アメリカ数学会紀要（英語版） 54 (10): 987?93. doi:10.1090/S0002-9904-1948-09121-2.
^ Tarjan, Robert Endre (1975-04-01). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM 22 (2): 215–225. doi:10.1145/321879.321884. ISSN 0004-5411. https://doi.org/10.1145/321879.321884.

参考文献

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". mathworld.wolfram.com (英語).

この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[1] 日本数学会編『岩波数学辞典第4版』（1版）岩波書店、2007年、334頁。ISBN 978-4000803090。

[Ack-2] Wilhelm Ackermann (1928). “Zum Hilbertschen Aufbau der reellen Zahlen”. Mathematische Annalen 99: 118–133. doi:10.1007/BF01459088.

[3] Cristian Calude, Solomon Marcus（英語版） and Ionel Tevy (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.

[4] Hilbert, David (1926-12-01). “Über das Unendliche” (ドイツ語). Mathematische Annalen 95 (1): 161–190. doi:10.1007/BF01206605. ISSN 1432-1807. https://doi.org/10.1007/BF01206605.

[5] von Heijenoort. From Frege To Godel Archived May 4, 2008, at the Wayback Machine., 1967.

[6] Raphael M. Robinson (1948). “Recursion and Double Recursion”. アメリカ数学会紀要（英語版） 54 (10): 987?93. doi:10.1090/S0002-9904-1948-09121-2.

[7] Tarjan, Robert Endre (1975-04-01). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM 22 (2): 215–225. doi:10.1145/321879.321884. ISSN 0004-5411. https://doi.org/10.1145/321879.321884.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

アッカーマン関数

目次

歴史

概念

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

逆アッカーマン関数

脚注

参考文献

関連項目

外部リンク