# Is there a "natural" example of a total, computable but non-primitive recursive function?

Every example of a total, computable but non-primitive recursive function seems to be explicitly constructed for proof theory, or in Godelian proofs of "what is the name of this book?" kind. But is there a non-primitive recursive function or algorithm that occurs naturally, like in physics or number theory or even in industry software?

• The standard example is the Ackermann function. My (possibly incorrect) understanding is that it was "contrived" for this purpose. However, its occurrence in other contexts such as in the asymptotic complexity of union-find and its relationship to things like arrow notations suggests that it is somewhat "natural" despite its origins. Jul 21 '17 at 0:27
• I don't know if you call it natural or not, but you can always just compute $R(x) = P_x(x) + 1$ where $P$ is an enumeration of your computing model, for any computing model with only total machines. By that definition, $\forall y ~:~ R \ne P_y$. Maybe that is what you mean by Godelian though. Jul 21 '17 at 6:06