Primitive Recursive Function - Limitations

Limitations

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial 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 total computable function — this can be seen with a variant of Cantor's diagonal argument. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

The primitive recursive functions of one argument (i.e., unary functions) can be computably enumerated. This enumeration uses the definitions of the primitive recursive functions (which are essentially just expressions with the composition and primitive recursion operations as operators and the basic primitive recursive functions as atoms), and can be assumed to contain every definition once, even though a same function will occur many times on the list (since many definitions define the same function; indeed simply composing by the identity function generates infinitely many definitions of any one primitive recursive function). This means that the n-th definition of a primitive recursive function in this enumeration can be effectively determined from n. Indeed if one uses some Gödel numbering to encode definitions as numbers, then this n-th definition in the list is computed by a primitive recursive function of n. Let f_n denote the unary primitive recursive function given by this definition.

Now define the "evaluator function" ev with two arguments, by ev(i,j) = f_i(j). Clearly ev is total and computable, since one can effectively determine the definition of f_i, and being a primitive recursive function f_i is itself total and computable, so f_i(j) is always defined and effectively computable. However a diagonal argument will show that the function ev of two arguments is not primitive recursive.

Suppose ev were primitive recursive, then the unary function g defined by g(i) = S(ev(i,i)) would also be primitive recursive, as it is defined by composition from the successor function and ev. But then g occurs in the enumeration, so there is some number n such that g = f_n. But now g(n) = S(ev(n,n)) = S(f_n(n)) = S(g(n)) gives a contradiction.

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article Machines that always halt. Note however that the partial computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.

Other examples of total recursive but not primitive recursive functions are known:

• The function that takes m to Ackermann(m,m) is a unary total recursive function that is not primitive recursive.
• The Paris–Harrington theorem involves a total recursive function that is not primitive recursive. Because this function is motivated by Ramsey theory, it is sometimes considered more "natural" than the Ackermann function.
• The Sudan function