原始再帰関数
再帰関数は、例えばμ作用素(英語版)を使って定義できる。μ作用素は入力に対して、出力が返ってくることを保証しない。このような関数を部分関数 (Partial Function) と言い、始域のどのような入力に対しても出力が返ってくる関数を全域関数 (Total Function) と言う。
原始再帰関数は全て全域再帰的であるが、全域再帰関数が全て原始再帰的とは言えない。アッカーマン関数 A(m,n) は全域再帰関数でありながら原始再帰的でない有名な例である。アッカーマン関数を使って、原始再帰関数が全域再帰関数の部分集合であるとする見方もある。この場合、関数が原始再帰的であるとは、その関数がチューリングマシンで計算可能で、かつある m に対して A(m, n)以下のステップ数で必ず停止するものと定義される。