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.

### Like this:

Like Loading...

*Related*

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.

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.