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 and composition? as central operations. 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]?).

Definition

Primitive recursive functions take natural numbers as arguments and produce a natural number. A function which takes n arguments is called n-ary?. They are defined as follows:

The initial set of axioms:

1. The constant? function 0 is primitive recursive.
2. The "successor function" S, which takes one argument and returns the succeeding number on the natural [number line]?, is primitive recursive.
3. The "projection functions" P_iⁿ, which take n arguments and return their ith argument, are primitive recursive.

The set of operators?:

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, 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.

The set of primitive recursive functions are the closure of the initial set of terms over these operators, i.e. the set of all functions that can be generated by repeated application of these rules to the basic functions defined above.

(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 straightforward. 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)

---

/Talk