1920年台後半、計算機の基礎研究を行っていたガブリエル・スーダン （英語版 ） ヴィルヘルム・アッカーマン （いずれもダフィット・ヒルベルト の教え子）は、「全域 計算可能 （または単に「再帰的」）であって原始再帰的 でない」関数の発見者であるとされている。始めに1927年にスーダンによりスーダン関数 が発表され、後の1928年にアッカーマンにより φ 関数が別々に発表された。アッカーマンの三変数関数 φ(m , n , p ) は、p = 0, 1, 2 のときそれぞれ加法 ・乗法 ・累乗 となる。
1920年台後半、ダフィット・ヒルベルト の教え子であったガブリエル・スーダン （英語版 ） ヴィルヘルム・アッカーマン は、計算機の基礎研究を行っていた。この二人は「全域 計算可能 （または単に「再帰的」）であって原始再帰的 でない」関数の発見者であるとされている。まず1927年にスーダンによりスーダン関数 が発表され、後の1928年にアッカーマンにより φ 関数が別々に発表された。アッカーマンの三変数関数 φ(m , n , p ) は、p = 0, 1, 2 のときそれぞれ加法 ・乗法 ・累乗 となる。
φ
(
m
,
n
,
0
)
=
m
+
n
φ
(
m
,
n
,
1
)
=
m
⋅
n
φ
(
m
,
n
,
2
)
=
m
n
{\displaystyle {\begin{aligned}\varphi (m,\,n,\,0)&=m+n\\\varphi (m,\,n,\,1)&=m\cdot n\\\varphi (m,\,n,\,2)&=m^{n}\end{aligned}}\,\!}
さらに p > 2 のとき φ はこれら算術演算の拡張、いわゆるハイパー演算 を与える。この φ はもともと「全域計算可能だが原始再帰的でない」関数として与えられたものである。φ には幾つかの変形が存在し、初等的な算術演算を累乗から先へ拡張するのに特化したもの（グッドスタインのハイパー演算列など）なども存在している。そのような関数ほどではないものの、φ も累乗から先への拡張を与える関数の一つと見做されている。
Über das Unendliche において、ヒルベルトは φ が原始再帰関数 でないと予想した。それに証明を与えたのは、彼の個人秘書でありまた OB でもあったアッカーマンである。この証明は Zum Hilbertschen Aufbau der reellen Zahlen において発表された。
後にロージャ・ペーテル （英語版 ） ラファエル・ロビンソン （英語版 ）
定義と性質 [ 編集 ] アッカーマンが最初に与えた三変数関数 φ(m , n , p ) は、非負整数 m , n , p に対して次のように再帰的に定義されるものである。
φ
(
m
,
n
,
p
)
=
{
φ
(
m
,
n
,
0
)
=
m
+
n
φ
(
m
,
0
,
1
)
=
0
φ
(
m
,
0
,
2
)
=
1
φ
(
m
,
0
,
p
)
=
m
for
p
>
2
φ
(
m
,
n
,
p
)
=
φ
(
m
,
φ
(
m
,
n
−
1
,
p
)
,
p
−
1
)
for
n
>
0
and
p
>
0.
{\displaystyle \varphi (m,\,n,\,p)={\begin{cases}\varphi (m,\,n,\,0)=m+n\\\varphi (m,\,0,\,1)=0\\\varphi (m,\,0,\,2)=1\\\varphi (m,\,0,\,p)=m&{\text{ for }}p>2\\\varphi (m,\,n,\,p)=\varphi {\Bigl (}m,\,\varphi (m,\,n-1,\,p),\,p-1{\Bigl )}&{\text{ for }}n>0{\text{ and }}p>0.\end{cases}}\,\!}
これの二変数版には幾つかの定義が存在し、中でもロージャ・ペーテル （英語版 ） ラファエル・ロビンソン （英語版 ） アッカーマン関数 と呼ばれる。
A
(
m
,
n
)
=
{
n
+
1
if
m
=
0
A
(
m
−
1
,
1
)
if
m
>
0
and
n
=
0
A
(
m
−
1
,
A
(
m
,
n
−
1
)
)
if
m
>
0
and
n
>
0.
{\displaystyle A(m,\,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,\,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A{\Bigl (}m-1,\,A(m,\,n-1){\Bigr )}&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}}
この計算が常に終了するかどうかは一見明らかでないが、再帰が深くなる度に m , n のどちらかが減少することからこの深さは有限である。n が 0 になる度に m が減少することから最終的には m も 0 になる[1] m が減少する際に n がどこまで増大するのかについては上限が存在せず、しばしば非常に巨大な値となる。
クヌースの矢印表記
A
(
m
,
n
)
=
2
↑
⋯
↑
⏟
m
−
2
(
n
+
3
)
−
3
=
2
↑
m
−
2
(
n
+
3
)
−
3
{\displaystyle A(m,\,n)=2\underbrace {\uparrow \cdots \uparrow } _{m-2}(n+3)-3=2\uparrow ^{m-2}(n+3)-3}
コンウェイのチェーン表記
m ≧ 3 のとき次が成り立つ。
A
(
m
,
n
)
=
(
2
→
(
n
+
3
)
→
(
m
−
2
)
)
−
3
{\displaystyle A(m,\,n)={\Bigl (}2\rightarrow (n+3)\rightarrow (m-2){\Bigr )}-3}
またこの式から、n > 2 のとき次のようになる。
2
→
n
→
m
=
A
(
m
+
2
,
n
−
3
)
+
3
{\displaystyle 2\rightarrow n\rightarrow m=A(m+2,\,n-3)+3}
^ より詳しく言うと、各深さにおける (m , n ) の全体は（非負整数の順序付け同様に）整列 であり、値は辞書式順序 に従って減少する。従って無限に深くなっていくことはできない。
