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

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

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

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

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

また、数学的な意味として、[[原始再帰関数]]でない[[μ再帰関数]]の実例として有名である。これを（[[再帰|再帰呼出し]]のない手続き型の）[[プログラミング言語]]の言葉で言えば、[[スタック]]を用いれば[[ループ_(プログラミング)|ループ]]を使ってアッカーマン関数を書き表すことができるが、ループだけでは書き表せないということである。

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

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

スーダンとアッカーマンの双方が[[部分写像#全域写像|全域]][[計算可能関数]]（いくつかの参考文献では単純に "再帰的"と呼ばれる）でありながら[[原始再帰関数|原始再帰的でない関数]]の発見に功績が有ったと信じられている<ref>{{cite journal | author=Cristian Calude, {{ill2|Solomon Marcus|en|Solomon Marcus}} and Ionel Tevy | journal = Historia Math. | title=The first example of a recursive function which is not primitive recursive | date=November 1979 | pages=380?84 | volume=6 | issue=4 | doi=10.1016/0315-0860(79)90024-7}}</ref>。

スーダンがあまり知られていない[[スーダン関数]]を公表し独立した後、1928年アッカーマンは自分の生み出した関数 <math>\varphi\,\!</math>（ギリシャ文字の[[Φ|ファイ]]）を公表する。その関数は3つの引数を必要とし <math>\varphi(m, n, p)\,\!</math> の様に表記された。<ref name="Ack">{{cite journal | author=Wilhelm Ackermann | journal=[[Mathematische Annalen]] | title=Zum Hilbertschen Aufbau der reellen Zahlen | year=1928 | volume=99 | pages=118?133 | url=http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009 | doi=10.1007/BF01459088}}</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変数形式のアッカーマン関数は、{{ill2|ラファエル・M・ロビンソン|en|Raphael M. Robinson}}と{{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>。

==概念==
<math>a+b, a\cdot b, a^b, \ldots</math> という[[列 (数学)|列]]を想定すると、その全ての項は ''b'' 個の ''a'' で演算を ''b'' − 1 回繰り返すことで、次項に変換される。（例えば第一項 <math>a+b</math> で行われた[[加算]]を ''b'' 個の ''a'' の ''b'' − 1 個間全てで行うと、第二項 <math>a\cdot b</math> と等価になる。）

: ''例''： 上記の列に <math>a=2,b=4</math> を代入すると、6, 8, 16, 65536, <math>2^{2^{.^{.^{.^{2}}}}}</math>(65536階立の指数タワー)　,&nbsp;... という数列となる。第5項目の数はすでに、[[観測可能な宇宙#内容物質|宇宙のすべての原子の推定数]]よりもはるかに大きい。

アッカーマン関数の背後には、この考え方があると思うべきである。オリジナルのアッカーマン関数 <math>\varphi</math> は、以下のリストを満たす関数である:
: <math>\varphi(a, b, 0) = a + b\,</math>
: <math>\varphi(a, b, 1) = a \cdot b</math>
: <math>\varphi(a, b, 2) = a^b\,</math>
: <math>\ldots</math>

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

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

{| class="wikitable"
|+ A(''m'',&nbsp;''n'') の値
|-
! ''m''{{Backslash}}''n''
! 0
! 1
! 2
! 3
! 4
! n
|-
! 0
| 1 || 2 || 3 || 4 || 5 || <math>n + 1</math>
|-
! 1
| 2 || 3 || 4 || 5 || 6 || <math>n + 2 = 2 + (n + 3) - 3</math>
|-
! 2
| 3 || 5 || 7 || 9 || 11 || <math>2n + 3 = 2 \times (n + 3) - 3</math>
|-
! 3
| 5 || 13 || 29 || 61 || 125 || <math>2^{n+3} - 3</math>
|-
! 4
| 13 || 65533
| 2<sup>65536</sup>&nbsp;&minus;&nbsp;3
| <math>{2^{2^{65536}}} - 3</math>
| A(3,&nbsp;A(4,&nbsp;3)) = 2<sup>2<sup>2<sup>65536</sup></sup></sup> − 3
| <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\text{ + 3 twos}\end{matrix}</math>
|-
! 5
| 65533 ||
<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\65536\text{ twos}\end{matrix}</math>
|| A(4,&nbsp;A(5,&nbsp;1))
| A(4,&nbsp;A(5,&nbsp;2)) || A(4,&nbsp;A(5,&nbsp;3)) || <math> \operatorname{A}(4, \operatorname{A}(5,n-1))</math>
|-
! 6
| A(5,&nbsp;1) || A(5,&nbsp;A(6,&nbsp;0))
| A(5,&nbsp;A(6,&nbsp;1))
| A(5,&nbsp;''A''(6,&nbsp;2)) || A(5,&nbsp;A(6,&nbsp;3)) || <math> \operatorname{A}(5, \operatorname{A}(6,n-1))</math>
|}

再帰的な参照で表示している値は非常に大きいが、[[クヌースの矢印表記]]、[[コンウェイのチェーン表記]]、[[ハイパー演算子]]等を使えば
:<math>\operatorname{Ack}(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} m (2, n+3)-3</math>
と簡潔に表す事が出来る。

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

{| class="wikitable"
|+ A(''m'',&nbsp;''n'') の値
|-
! ''m''{{Backslash}}''n''
! 0
! 1
! 2
! 3
! 4
! n
|-
! 0
| 0+1 || 1+1 || 2+1 || 3+1 || 4+1 || <math>n + 1</math>
|-
! 1
| A(0,1) || A(0,A(1,0)) || A(0,A(1,1)) || A(0,A(1,2)) || A(0,A(1,3)) || <math>n + 2 = 2 + (n + 3) - 3</math>
|-
! 2
| A(1,1) || A(1,A(2,0)) || A(1,A(2,1)) || A(1,A(2,2)) || A(1,A(2,3)) || <math>2n + 3 = 2 \times (n + 3) - 3</math>
|-
! 3
| A(2,1) || A(2,A(3,0)) || A(2,A(3,1)) || A(2,A(3,2)) || A(2,A(3,3)) || <math>2^{n+3} - 3</math>
|-
! 4
| A(3,1) || A(3,A(4,0)) || A(3,A(4,1)) || A(3,A(4,2)) || A(3,A(4,3)) ||
<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\text{ + 3 twos}\end{matrix}</math>
|-
! 5
| A(4,1) || A(4,A(5,0)) || A(4,A(5,1)) || A(4,A(5,2)) || A(4,A(5,3)) ||
<math> \operatorname{A}(4, \operatorname{A}(5,n-1))</math>
|-
! 6
| A(5,1) || A(5,A(6,0)) || A(5,A(6,1)) || A(5,A(6,2)) || A(5,A(6,3)) ||
<math> \operatorname{A}(5, \operatorname{A}(6,n-1))</math>
|}

== 関連項目 ==
* [[巨大数]]
* [[ヴィルヘルム・アッカーマン]]
* [[竹内関数]]
*{{仮リンク|グッドスタイン関数|en|Goodstein function|label=グッドスタイン関数}}
* [[素集合データ構造]]
* [[二重再帰法]]
* [[急増加関数]]

== 脚注 ==
{{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)

== 外部リンク ==
* Weisstein, Eric W. "[http://mathworld.wolfram.com/AckermannFunction.html Ackermann Function]." From ''[[MathWorld]].'' {{en icon}}

{{巨大数}}

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