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

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.

2 comments on “How I learned to stop worrying about Turing completeness and love primitive recursion”

1. Dan P says:

Some extra points to mention:

Primitive recursion corresponds to the ordinals less than omega^omega. (Paper here: http://www.science20.com/mark_changizi/why_we_have_eureka_moments Pointed out to me by @TomDuff on Twitter)

I first met primitive recursion in GEB through the language BlooP. http://en.wikipedia.org/wiki/BlooP_and_FlooP When people (at least imperative programmers) ask me what PR means I just send them there.

2. Dan, thanks for the links; the first one seems really interesting. I knew of BlooP and FlooP, but didn’t mention them because I’ve never really read GEB, and the article on Wikipedia isn’t very detailed.

P.S. Sorry if your comment didn’t appear immediately; apparently the moderation policy was a bit too strict.