# What is the significance of primitive recursive functions?

I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive functions?

• Some related questions: 1, 2, 3. As for your question, in which direction would you like to have us interpret "significance"? Historically, in computability theory, in practice, ...? – Raphael Apr 27 '14 at 19:46
• @Raphael Yuval Filmus provides some computer theoretical insight on the matter, but if you do have knowledge of its historical significance, that would also be interesting. – Untitled Apr 28 '14 at 0:27

The halting problem is undecidable, but one might object that for most programs, it is easy to check whether they halt or not, by looking for any obvious infinite loops. Conversely, if you wanted to ensure that your program always terminates, you could do so by bounding a priori the number of loop iterations for every loop. For example, consider the pseudocode for repeated squaring:

def power(x, y, p):
"compute x^y mod p"
assert y >= 0
result = 1
while y > 0:
if x is odd: result = result * x (mod p)
y = y div 2
x = x * x
return result


How do we know that this procedure always terminates? One way would be to a priori bound the loop:

def power(x, y, p):
"compute x^y mod p"
assert y >= 0
bound = y
result = 1
loop bound times:
if x is odd: result = result * x (mod p)
y = y div 2
x = x * x
if y == 0: break
return result


Now it's clear that this program terminates, and if we haven't made a mistake elsewhere, the two programs would produce the same output.

Primitive recursive functions are those computed by programs in which all loops are bounded and there is no recursion.

While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:

1. Is every computable function presentable in this form?
2. If not, what is the relation between this class and all computable functions?

To answer 1, one can show that certain computable functions which grow "too fast" are not primitive recursive, for example the Ackermann function. Conversely, every function whose growth rate is "reasonable" is primitive recursive. And every computable function can be stated in the form $f(x) = \psi(\min_y \phi(x,y))$ for primitive recursive $\phi,\psi$, where we think of $\phi$ as a predicate.

• 1) Every such bound has to be computable by primitive recursive functions. 2) Explaining the term "primitive recursion" by saying "use no recursion" is odd. We can use recursion, just not any kind. – Raphael Apr 27 '14 at 19:48
• @Raphael 1) Bounded by another variable. 2) The recursion alluded to in the name is represented by the loops. Terminology need not be coherent, after all computable functions are also called recursive functions, but Turing machines allow no (overt) recursion. – Yuval Filmus Apr 27 '14 at 20:51

When I took my computability course, we were introduced to this in the following way:

Primitive recursion is a natural way of defining a computation (probably obvious if you have a math mind, for a programmer it's easier to understand that recursion is a loop backwards).

So once you master primitive recursion, you wonder: is that all there is in computation?

Well, it turns out it's not. First, you're missing undefined values. Ok,so you can extend primitive recursion to partial primitive recursive functions.

Still, there are some (complete) computable functions that are not primitive recursive. Well, Ackermann is one of it. So that is why the Ackermann function is important. It turns out that 'recursion' is "primitive recursion + minimization", and while it cannot be proven, it seems, that's all there is to computation.

So primitive recursive functions are important as they are

1. simple formalism
2. base for the definition of recursion

Not sure - maybe someone else will know - but I think before Ackermann came up with his function, mathematicians thought that computable = primitive recursion + partial functions.