Primitive recursive function

Primitive recursive functions are a class of functions which, while a subset of the recursive? functions (which are exactly those functions which we call "computable?" -- see [Equivalence of models of computation]?), are an important building block on the way to a full formalization of computability.

Primitive recursive functions are functions from natural numbers to natural numbers, defined as follows (from here on we will write "p.r." for primitive recursive):

Take as axioms the initial set of numbers and functions:

1. The constant? 0 is p.r.
2. The "successor function" S is p.r.
3. The "projection functions" P_iⁿ are p.r.

Where the "successor function" takes the number k and returns the number one greater than k on the natural [number line]?, and the "projection functions" P_iⁿ take n arguments and return the ith one.

Now consider the following operations:

1. Composition: Given f a k-ary? p.r. function and k l-ary functions g₀,...,g_k-1 p.r. functions, the composition? of f with g₀,...,g_k-1 is p.r., i.e. the function h(x₀,...,x₁)=f(g₀(x₀,...,x₁),...,g_k-1(x₀,...,x_l-1)) is p.r.
2. Primitive recursion: Given f a k-ary p.r. function and g a (k+2)-ary p.r. function, then the (k+1)-ary function defined as the primitive recursion of f and g is p.r., i.e. the function h where h(0,x₀,...,x_k-1)=f(x₀,...,x_k-1) and h(n+1,x₀,...,x_k-1)=g(n,h(n,x₀,...,x_k-1),x₀,x_k-1)) is p.r.

The closure of the operations over the initial set of numbers and functions forms the set of p.r. functions.

(Note that the projection functions allow us to get around the apparent rigidity in terms of the arity of the functions above, as via composition we can pass any subset of the arguments.)

Example P.R. definitions

1. addition
2. subtraction?
3. exponentiation?

(need actual definitions)

P.R. functions are a subset of the recursive functions

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial set of functions are intuitively computable (in their very simplicity), and the two operations by which one can create new p.r. functions are also very straight-forward. However the set of p.r. functions does not include every possible computable function -- this can be seen with a variant of Cantor's diagonalization argument.

(need outline of proof)