Primitive recursive function

Primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using recursion as the central operation. The primitive recursive functions are a subset of the recursive? functions (which are exactly those functions which we call "computable?" -- see [Equivalence of models of computation]?).

Primitive recursive functions are functions which take one or several natural numbers as arguments and produce a natural number as value. A function which takes n arguments will be called n-ary. They are defined as follows.

Start with the following functions:

1. The constant? function 0 is primitive recursive.
2. The "successor function" S, defined by S(k) = k + 1, is primitive recursive.
3. The "projection functions" P_iⁿ, a function of n arguments which returns its ith argument, are primitive recursive.

Now consider the following operations:

1. Composition: Given f a k-ary primitive recursive function and k l-ary primitive recursive functions g₀,...,g_k-1, the composition? of f with g₀,...,g_k-1, i.e. the function h(x₀,...,x_l-1)=f(g₀(x₀,...,x_l-1),...,g_k-1(x₀,...,x_l-1)), is primitive recursive.
2. Primitive recursion: Given f a k-ary primitive recursive function and g a (k+2)-ary primitive recursive function, then the (k+1)-ary function defined as the primitive recursion of f and g, 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 primitive recursive.

All functions that can be generated by repeated application of these rules to the basic functions defined above form the set of primitive recursive 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 primitive recursive functions===

1. addition
2. subtraction?
3. exponentiation?

(need actual definitions)

===Primitive recursive 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 primitive recursive functions are also very straight-forward. However the set of primitive recursive functions does not include every possible computable function -- this can be seen with a variant of Cantor's diagonalization argument.

(need outline of proof)