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.

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