アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数 m と n に対し、 A ( m , n ) = { n + 1 ,  if  m = 0 A ( m − 1 , 1 ) ,  if  n = 0 A ( m − 1 , A ( m , n − 1 ) ) ,  otherwise {\displaystyle 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年アッカーマンは自分の生み出した関数 φ {\displaystyle \varphi \,\!} を公表する。その関数は3つの引数を必要とし φ ( m , n , p ) {\displaystyle \varphi (m,n,p)\,\!} の様に表記された[2]。スーダンとアッカーマンの双方が全域計算可能関数（いくつかの参考文献では単純に "再帰的"と呼ばれる）でありながら原始再帰的でない関数の発見に功績が有ったと信じられている[3]。

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

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

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

φ ( a , b , 0 ) = a + b φ ( a , 0 , n + 1 ) = { n ( if   n = 0 , 1 ) a ( otherwise ) φ ( a , b + 1 , n + 1 ) = φ ( a , φ ( a , b , n + 1 ) , n ) {\displaystyle {\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}}}

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

φ ( a , b , 0 ) = a + b φ ( a , b , 1 ) = 0 + a + ⋯ + a ⏟ b times = a ⋅ b φ ( a , b , 2 ) = 1 ⋅ a ⋅ ⋯ ⋅ a ⏟ b times = a b φ ( a , b , 3 ) = a a ⋅ ⋅ ⋅ a ⏟ ( b + 1 ) times ⋮ {\displaystyle {\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\n01234n
012345n+1
1A(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))
2A(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))
3A(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\n01234n
012345n + 1
123456n + 2 = 2 + (n + 3) - 3
2357911 2 n + 3 = 2 × ( n + 3 ) − 3 {\displaystyle 2n+3=2\times (n+3)-3}
35132961125 2 n + 3 − 3 {\displaystyle 2^{n+3}-3}
41365533 2 65536 − 3 {\displaystyle 2^{65536}-3} 2 2 65536 − 3 {\displaystyle {2^{2^{65536}}}-3} 2 2 2 65536 − 3 {\displaystyle 2^{2^{2^{65536}}}-3} 2 2 ⋅ ⋅ ⋅ 2 ⏟ − 3 n  + 3 twos {\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\text{ + 3 twos}}\end{matrix}}}