Any examples of total recursive functions that are not primitive recursive and do not violently explode?
The set of primitive recursive functions is interesting because it is pretty inclusive, (lots of functions have a primitive recursive implementation) and primitive recursive functions always terminate. I’m interested in trying to implement general purpose machine learning by enumerating primitive recursive functions. Which raises the question of just how general the primitive recursive functions really are.
Ackermann’s function gives an example of what you miss out when you confine yourself to primitive recursive functions. But Ackermann’s function explodes violently. The values of the function rapidly become too large for any practical use. If that were typical, I would think that I miss out on nothing of practical importance when I restrict myself to primitive recursive functions.
But I suspect that the violent explosion is only there to meet the needs of the proof. Given a function that is specified by an implementation that is not primitive recursive, how can you tell whether it is primitive recursive? There might be a clever primitive recursive way of implementing the function that is hard to find. One needs to come up with a proof, and that is also hard to find. The violent explosion of Ackermann’s function lets one construction a proof; no primitive recursive function goes BOOM! quite as dramatically.
Are there any other proof techniques and hence other, more practically important, functions that are (known to be) total recursive but not primitive recursive?
The inverse of the Ackermann function grows very slowly but is not primitive recursive. That is, the function f where f(n) is the smallest m such that A(m) exceeds n. Of course, this is hardly a different method of proof.
Any examples of total recursive functions that are not primitive recursive and do not violently explode?
The set of primitive recursive functions is interesting because it is pretty inclusive, (lots of functions have a primitive recursive implementation) and primitive recursive functions always terminate. I’m interested in trying to implement general purpose machine learning by enumerating primitive recursive functions. Which raises the question of just how general the primitive recursive functions really are.
Ackermann’s function gives an example of what you miss out when you confine yourself to primitive recursive functions. But Ackermann’s function explodes violently. The values of the function rapidly become too large for any practical use. If that were typical, I would think that I miss out on nothing of practical importance when I restrict myself to primitive recursive functions.
But I suspect that the violent explosion is only there to meet the needs of the proof. Given a function that is specified by an implementation that is not primitive recursive, how can you tell whether it is primitive recursive? There might be a clever primitive recursive way of implementing the function that is hard to find. One needs to come up with a proof, and that is also hard to find. The violent explosion of Ackermann’s function lets one construction a proof; no primitive recursive function goes BOOM! quite as dramatically.
Are there any other proof techniques and hence other, more practically important, functions that are (known to be) total recursive but not primitive recursive?
The inverse of the Ackermann function grows very slowly but is not primitive recursive. That is, the function f where f(n) is the smallest m such that A(m) exceeds n. Of course, this is hardly a different method of proof.