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?
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:
- Is every computable function presentable in this form?
- 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.
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
- simple formalism
- 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.