11 July 2010

The primitive recursive functions are a class of computable arithmetic functions with a reasonably natural definition. They do not exhaust all computable functions (e.g., Ackermann’s function grows faster than any PR function). Here is a list of reasons to like them anyway.

- The PR functions are exactly the functions that can be computed by using only
*for*loops (i.e., without unbounded kinds of loop such as*while*and*repeat-until*). - Each time you apply the primitive recursion schema, you get new functions. Meaning: with
*n*+ 1 nested*for*loops you can compute functions that you can't compute using only*n*nested*for*loops. - Any computable function can be obtained by using PR functions plus a single application of the
*μ*operator. In other words, you just need to use one*while*loop (together with the*for*loops) to obtain a Turing machine. This is called Kleene's normal form theorem. - Every recursively enumerable set is also primitively recursively enumerable. See this question on MathOverflow, where I recently discovered this fact.
- The PR functions are exactly the functions that can be computed by Turing machines operating within a PR time bound. Isn't this amazing? See, e.g., this paper by A.R. Meyer and D.M. Ritchie (yes, that D.M. Ritchie).
- Any function of practical use is primitive recursive. This is a consequence of the previous point: polynomials, but also exponentials (and much, much worse functions) are all PR. If a function is not PR, then you don't have enough time to compute it.

I strongly urge you to like the primitive recursive functions too.