原始再帰関数
原始再帰関数は整数ではなく自然数を扱うもので、減算は自然数の範囲では閉じていないため、ここでは限定された減算関数を扱う。限定された減算関数 sub(a, b) は b - a が負でなければその値を返し、負の場合は 0 を返す。
後者関数の反対の動作をする前者関数 (Predecessor Function) を次のように再帰的に定義する:
pred(0)=0,
pred(n + 1) = n.
これを原始再帰関数の形式的定義となるよう変換すると、次のようになる:
pred(0)=0,
pred(S(n)) = P2(pred(n), n).
限定された減算関数は、この前者関数を使って定義される。ちょうど後者関数を使って加算が定義されるのと似ている:
sub(0, x) = P1(x),
sub(S(n), x) = pred(P1(sub(n, x), n, x)).
ここで sub(a, b) は b - a を表している。原始再帰的定義を単純化するために引数の順番を一般的なものと逆にしている。これは適当な射影の合成で容易に修正できる。
他にも冪乗や素数判定が原始再帰関数である。原始再帰関数 e, f, g, h があるとき、e ≤ f ならば g の値を返し、そうでないとき h の値を返す関数も原始再帰的である。
合成 (Composition) : k 項原始再帰関数 f と k 個の m 項原始再帰関数 g1, ..., gk について、f と g1, ..., gk の合成関数、すなわち m 項関数 h(x1, ..., xm) = f(g1(x1, ..., xm), ..., gk(x1, ..., xm)) は原始再帰的である。
原始再帰法 (Primitive Recursion) : k 項原始再帰関数 f と (k + 2) 項原始再帰関数 g について、f と g の原始再帰として定義される (k + 1) 項関数、すなわち、h(0, x1, ..., xk) = f(x1, ..., xk) 、 h(S(n), x1, ..., xk) = g(h(n, x1, ..., xk), n, x1, ..., xk) であるような関数 h は原始再帰的である。
上述の基本的な関数と、それに上述の作用素を有限回適用して得られる関数だけが原始再帰的関数である。