アッカーマン関数
アッカーマン関数(アッカーマンかんすう、英: 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}}}
によって定義される関数のことである。
与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。
また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを(再帰呼出しのない手続き型の)プログラミング言語の言葉で言えば、アッカーマン数をプログラムで計算することはできるが、While文を使わずFor文のみでそれを計算することができない、ということになる。
1920年代後半、数学者ダフィット・ヒルベルトの教導を受けていた学生だったガブリエル・スーダン(英語版)とヴィルヘルム・アッカーマンは、計算の基礎を研究していた。ヒルベルトは、すべての計算可能関数が 原始再帰的であると仮定していた。簡単に言えば、これは、コンピューターで計算できる各関数をいくつかの非常に単純なルールからまとめて、計算の期間を事前に推定できることを意味する。実際にこれは人々が利用するほとんどの関数に適用出来るが、2人の研究はそれを覆した。
1927年に、スーダンはスーダン関数を発表した。それとは独立に、1928年アッカーマンは自分の生み出した関数 φ {\displaystyle \varphi \,\!} を公表する。その関数は3つの引数を必要とし φ ( m , n , p ) {\displaystyle \varphi (m,n,p)\,\!} の様に表記された。スーダンとアッカーマンの双方が全域計算可能関数(いくつかの参考文献では単純に "再帰的"と呼ばれる)でありながら原始再帰的でない関数の発見に功績が有ったと信じられている。
ヒルベルトはÜber das Unendlicheの中でアッカーマン関数が原始再帰的では無いと仮定したが、この仮説は彼の個人秘書となっていたアッカーマンによって実際に証明され、ヒルベルトの執筆した実数の論文上に掲載された。
2変数形式に単純化されたアッカーマン関数は、1935年ペーテル・ロージャ(英語版)によって開発された。