アッカーマン関数のソースを表示

'''アッカーマン関数'''（アッカーマンかんすう、{{lang-en-short|Ackermann function}}、{{lang-de-short|Ackermannfunktion}}）とは、非負[[整数]] ''m'' と ''n'' に対し、

:<math>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}</math>

によって定義される[[関数 (数学)|関数]]のことである<ref>{{Cite book|和書|editor=[[日本数学会]]|year=2007 |title=[[岩波数学辞典]]第4版 |edition=1 |publisher=[[岩波書店]]||page=334 |isbn=978-4000803090}}</ref>。

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

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

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

[[1927年]]に、スーダンは[[スーダン関数]]を発表した。それとは独立に、[[1928年]]アッカーマンは自分の生み出した関数 <math>\varphi\,\!</math> を公表する。その関数は3つの引数を必要とし <math>\varphi(m, n, p)\,\!</math> の様に表記された<ref name="Ack">{{cite journal|author=Wilhelm Ackermann|year=1928|title=Zum Hilbertschen Aufbau der reellen Zahlen|url=http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009|journal=[[Mathematische Annalen]]|volume=99|pages=118&ndash;133|doi=10.1007/BF01459088}}</ref>。スーダンとアッカーマンの双方が[[部分写像#全域写像|全域]][[計算可能関数]]（いくつかの参考文献では単純に "再帰的"と呼ばれる）でありながら[[原始再帰関数|原始再帰的でない関数]]の発見に功績が有ったと信じられている<ref>{{cite journal|author=Cristian Calude, {{ill2|Solomon Marcus|en|Solomon Marcus}} and Ionel Tevy|date=November 1979|title=The first example of a recursive function which is not primitive recursive|journal=Historia Math.|volume=6|issue=4|pages=380?84|doi=10.1016/0315-0860(79)90024-7}}</ref>。

ヒルベルトは''Über das Unendliche''<ref>{{Cite journal|last=Hilbert|first=David|date=1926-12-01|title=Über das Unendliche|url=https://doi.org/10.1007/BF01206605|journal=Mathematische Annalen|volume=95|issue=1|pages=161–190|language=de|doi=10.1007/BF01206605|issn=1432-1807}}</ref>の中でアッカーマン関数が原始再帰的では無いと仮定したが、この仮説は彼の個人秘書となっていたアッカーマンによって実際に証明され、ヒルベルトの執筆した実数の論文上に掲載された<ref name="Ack" /><ref>von Heijenoort. [http://mathgate.info/cebrown/notes/vonHeijenoort.php From Frege To Godel] {{webarchive |url=https://web.archive.org/web/20080504224223/http://mathgate.info/cebrown/notes/vonHeijenoort.php |date=May 4, 2008 }}, 1967.</ref>。

2変数形式に単純化されたアッカーマン関数は、[[1935年]]{{ill2|ペーテル・ロージャ|en|Rózsa Péter}}によって開発された<ref>{{cite journal | author=Raphael M. Robinson | title=Recursion and Double Recursion | journal={{ill2|アメリカ数学会紀要|en|Bulletin of the American Mathematical Society}} | year=1948 | volume=54 | pages=987?93 | url=http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bams/1183512393&page=record | doi=10.1090/S0002-9904-1948-09121-2 | issue=10}}</ref>。

==概念==
アッカーマンが1928年に発表した3変数の関数は次のような定義である<ref name="Ack" />：

<math>\begin{align}
\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{align}</math>

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

<math>\begin{align}
\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{align}</math>

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

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

{| class="wikitable"
|+
A(''m'',''n'') の値
|-
! ''m''{{Backslash}}''n''
! 0
! 1
! 2
! 3
! 4
! n
|-
! 0
| {{Math|1}} || {{Math|2}} || {{Math|3}} || {{Math|4}} || {{Math|5}} || {{Math|''n''+1}}
|-
! 1
| {{Math|''A''(0, 1)}} || {{Math|''A''(0, ''A''(1, 0))}} || {{Math|''A''(0, ''A''(1, 1))}} || {{Math|''A''(0, ''A''(1, 2))}} || {{Math|''A''(0, ''A''(1, 3))}} || {{Math|''A''(0, ''A''(1, ''n''-1))}}
|-
! 2
| {{Math|''A''(1, 1)}} || {{Math|''A''(1, ''A''(2, 0))}} || {{Math|''A''(1, ''A''(2, 1))}} || {{Math|''A''(1, ''A''(2, 2))}} || {{Math|''A''(1, ''A''(2, 3))}} || {{Math|''A''(1, ''A''(2, ''n''-1))}}
|-
! 3
| {{Math|''A''(2, 1)}} || {{Math|''A''(2, ''A''(3, 0))}} || {{Math|''A''(2, ''A''(3, 1))}} || {{Math|''A''(2, ''A''(3, 2))}} || {{Math|''A''(2, ''A''(3, 3))}} || {{Math|''A''(2, ''A''(3, ''n''-1))}}
|-
! ︙
| {{Math|︙}} || ︙ || ︙ || ︙ || ︙ ||
︙
|}
計算できる範囲で具体的な数値に置き換えていくと、表は次のようになる。

{| class="wikitable"
|+ A(''m'',''n'') の値
|-
! ''m''{{Backslash}}''n''
! 0
! 1
! 2
! 3
! 4
! n
|-

! 0
| {{Math|1}}|| {{Math|2}}|| {{Math|3}}|| {{Math|4}}|| {{Math|5}}|| {{Math|''n'' + 1}}
|-
! 1
| {{Math|2}}||{{Math|3}}
| {{Math|4}}|| {{Math|5}}|| {{Math|6}}|| {{Math|1=''n'' + 2 = 2 + (''n'' + 3) - 3}}
|-
! 2
| {{Math|3}}|| {{Math|5}}|| {{Math|7}}|| {{Math|9}}|| {{Math|11}}|| <math>2n + 3 = 2 \times (n + 3) - 3</math>
|-
! 3
| {{Math|5}}|| {{Math|13}}|| {{Math|29}}|| {{Math|61}}|| {{Math|125}}|| <math>2^{n+3} - 3</math>
|-
! 4
| {{Math|13}}|| {{Math|65533}}
| <math>2^{65536} - 3</math>
| <math>{2^{2^{65536}}} - 3</math>
| <math>2^{2^{2^{65536}}} - 3</math>
| <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\text{ + 3 twos}\end{matrix}</math>

|-
! 5
| {{Math|65533}}||
<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\65536\text{ twos}\end{matrix}</math>
|| <math>A(4, A(5, 1))</math>
| <math>A(4, A(5, 2))</math>|| <math>A(4, A(5,3))</math>|| <math> A(4, A(5,n-1))</math>
|}

一般の値は非常に大きいが、[[クヌースの矢印表記]]、[[コンウェイのチェーン表記]]、[[ハイパー演算子]]等を使えば
:<math>A(m, n)</math>
::<math> = \left( 2\uparrow^{m-2} \left(n+3 \right) \right) -3</math>
::<math> = \left( 2\rightarrow \left(n+3 \right) \rightarrow \left(m-2 \right) \right) -3</math>
::<math> = \operatorname{hyper}(2, m, n+3)-3</math>
::<math> = \operatorname{hyper\mathit{m}} (2, n+3)-3</math>
と簡潔に表す事が出来る。

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

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

[[ロバート・タージャン]]の1975年の論文において提唱された[[素集合データ構造]] (Union-Find) の探索および結合アルゴリズムについて、その計算量が <math>O(\alpha(n))</math> で見積もられた<ref>{{Cite journal|last=Tarjan|first=Robert Endre|date=1975-04-01|title=Efficiency of a Good But Not Linear Set Union Algorithm|url=https://doi.org/10.1145/321879.321884|journal=Journal of the ACM|volume=22|issue=2|pages=215–225|doi=10.1145/321879.321884|issn=0004-5411}}</ref>。

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

<!--
== 多変数アッカーマン関数 ==
{{出典の明記| date = 2021年3月| section = 1}}
[[2ちゃんねる]]の巨大数探索[[スレッドフロート型掲示板|スレッド]]において、アッカーマン関数を多変数に拡張した'''多変数アッカーマン関数'''が定義された。

=== 定義 ===
[[多変数関数]]<math>A(a,b,...,y,z)</math>を以下のように定義する。

:<math>A(M,a)=a+1</math>

:<math>A(N,b+1,0,M,a)=A(N,b,a,M,a)</math>

:<math>A(N,b+1,0)=A(N,b,1)</math>

:<math>A(N,b+1,a+1)=A(N,b,A(N,b+1,a))</math>           

::(<math>a,b:</math><math>0</math>以上の任意の整数, <math>M:</math><math>0</math>個以上の<math>0</math>, <math>N:</math><math>0</math>個以上の<math>0</math>以上の整数)<ref>{{Cite book |和書 |author=フィッシュ |year=2017 |title=巨大数論 第2版 |publisher=インプレス R&D |location=東京 | url=http://gyafun.jp/ln/ |isbn=9784802093194 |pages=81-82}}</ref>

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

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

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

:<math>\{n,2,b+1,c+1,d+1,e+1,\cdots\}\fallingdotseq A(\cdots,e,d,c,b,n)</math>

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

:<math>\{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))</math>（括弧は{{math|''a''-1}}重）

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

配列表記と多変数アッカーマン関数を比較すると、両者には次のような違いがあるが、最終的な振る舞いや特徴は似ている。
*配列表記では 1 が最小の数だが、多変数アッカーマンでは 0 が最小の数となっている。
*数を並べる順番が左右逆になっている。配列表記では右の数の方が数を大きくする効果が大きく、多変数アッカーマンではその逆である。
*配列表記では末尾が1になるとそれが消えるが、多変数アッカーマン関数では先頭が0になると実質的にそれが消える。
*配列表記は {a,b} = a<sup>b</sup> の 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つ右の数だけ変わる。
特に最後の点がだいぶ違うように見えるが、多変数アッカーマン関数でも
<nowiki>
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)
</nowiki>
のように、結局は1つずつ数が変わっていくので、本質的にはそれほど変わらない。

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

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* 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)

== 関連項目 ==
* [[ヴィルヘルム・アッカーマン]]
* {{仮リンク|グッドスタイン関数|en|Goodstein function|label=グッドスタイン関数}}
* [[素集合データ構造]]
* [[二重再帰法]]
* [[巨大数]]
* [[急増加関数]]
* [[ハイパー演算子]]
* [[クヌースの矢印表記]]
* [[コンウェイのチェーン表記]]
* [[配列表記]]

== 外部リンク ==
* {{高校数学の美しい物語|1010|巨大数：アッカーマン関数とは}}
* {{MathWorld |title=Ackermann Function |urlname=AckermannFunction}}

{{Mathlogic-stub}}
{{巨大数}}

{{DEFAULTSORT:あつかあまんかんすう}}
[[Category:算術]]
[[Category:巨大数]]
[[Category:組合せ論]]
[[Category:特殊関数]]
[[Category:計算理論]]
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]