アッカーマン関数

アッカーマン関数（アッカーマンかんすう、英: 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]

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

また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを（再帰呼出しのない手続き型の）プログラミング言語の言葉で言えば、アッカーマン数をプログラムで計算することはできるが、While文を使わずFor文のみでそれを計算することができない、ということになる。

歴史編集

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年の論文において提唱された素集合データ構造の探索および結合アルゴリズムについて、その計算量が $O(\alpha (n))$ で見積もられた^[7]。

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

多変数アッカーマン関数編集

2ちゃんねるの巨大数探索スレッドにおいて、アッカーマン関数を多変数に拡張した多変数アッカーマン関数が定義された。

定義編集

多変数関数 $A(a,b,...,y,z)$ を以下のように定義する。

A(M,a)=a+1

A(N,b+1,0,M,a)=A(N,b,a,M,a)

A(N,b+1,0)=A(N,b,1)

A(N,b+1,a+1)=A(N,b,A(N,b+1,a))

(

a,b:

0

以上の任意の整数,

M:

0

個以上の

0

,

N:

0

個以上の

0

以上の整数)^[8]

この関数は、本質的には通常のアッカーマン関数に: $A(N,b+1,0,M,a)=A(N,b,a,M,a)$ のルールが追加されただけで、あとの3行は通常のアッカーマン関数の前に飾りが付いただけのものである。

この関数は $n$ 変数関数 $(A(\underbrace {x,0,0,...,0,x} _{n}))$ が急増加関数で $f_{\omega ^{n-1}}(x)$ 程度の強さとなる。これは配列表記（非拡張）と同じくらいの強さであり、3変数でコンウェイのチェーン表記レベル、4変数でピーター・ハーフォードによる拡張チェーン表記（あるいは回転矢印表記）レベルの巨大数となり、5変数以上になるとそのレベルを超える。

配列表記と多変数アッカーマン関数の間には近似関係があり、次のような式で表される。まず、配列表記の2変数目が2の場合は、

\{n,2,b+1,c+1,d+1,e+1,\cdots \}\fallingdotseq A(\cdots ,e,d,c,b,n)

次に、配列表記の2変数目が3以上の場合は、

\{n,a,b+1,c+1,d+1,e+1,\cdots \}\fallingdotseq A(\cdots ,e,d,c,b,A(\cdots ,e,d,c,b,\cdots ,A(\cdots ,e,d,c,b,n)\cdots ))

（括弧は

a -1

重）

ただし、配列表記では先頭が1ならその値は1に、4変数以上で先頭が2ならば、2変数目が1であれば2、2変数目が1でなければ4になってしまうし、更に配列表記では0も要素として使えないので、多変数アッカーマン関数においてnが2以下の場合はこの近似式は直接適用できない。

配列表記と多変数アッカーマン関数を比較すると、両者には次のような違いがあるが、最終的な振る舞いや特徴は似ている。

配列表記では 1 が最小の数だが、多変数アッカーマンでは 0 が最小の数となっている。
数を並べる順番が左右逆になっている。配列表記では右の数の方が数を大きくする効果が大きく、多変数アッカーマンではその逆である。
配列表記では末尾が1になるとそれが消えるが、多変数アッカーマン関数では先頭が0になると実質的にそれが消える。
配列表記は {a,b} = a^b の 2 変数関数が基本となり、多変数アッカーマンは A(a) = a+1 の 1 変数関数（後者関数）が基本となっている。
配列表記では {a,b,1,…,1,c,d…,n} ={a,a,a,…,{a,b−1,1,…,1,c,d, …,n},c−1,d,…,n}と、前の数が全部 a に変わる。多変数アッカーマンでは A(N,b+1,0,M,a) = A(N,b,a,M,a)と、1つ右の数だけ変わる。

特に最後の点がだいぶ違うように見えるが、多変数アッカーマン関数でも A(2,0,0,0,0,5) = A(1,5,0,0,0,5) = A(1,4,5,0,0,5) = A(1,4,4,5,0,5) = A(1,4,4,4,5,5) のように、結局は1つずつ数が変わっていくので、本質的にはそれほど変わらない。

また、多変数アッカーマン関数を更に拡張したものとして、「2重リストアッカーマン関数」や、「多重リストアッカーマン関数」といったものも考えられている。

脚注編集

^ 日本数学会編『岩波数学辞典第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.
^ フィッシュ『巨大数論第2版』インプレス R&D、東京、2017年、81-82頁。ISBN 9784802093194。http://gyafun.jp/ln/。

参考文献編集

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. （英語）

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

[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.

[8] フィッシュ『巨大数論第2版』インプレス R&D、東京、2017年、81-82頁。ISBN 9784802093194。http://gyafun.jp/ln/。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]