How I learned to stop worrying about Turing completeness and love primitive recursion

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.