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:
How do we know that this procedure always terminates? One way would be to a priori bound the loop:
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.
While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:
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
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.