アッカーマン関数

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

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

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

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

歴史

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

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

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

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

概念

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

${\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))$で見積もられた。

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

多変数アッカーマン関数

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$以上の整数)

この関数は、本質的には通常のアッカーマン関数に:$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重リストアッカーマン関数」や、「多重リストアッカーマン関数」といったものも考えられている。

関連項目

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

参考文献

• 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 (英語).