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?

  • 3
    $\begingroup$ 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. $\endgroup$ Jul 21 '17 at 0:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – DanielV
    Jul 21 '17 at 6:06

This answer gives us a hint, namely that an interpreter for a language more powerful than primitive recursion, is itself not primitive recursive. For example, System F has no self-interpreter, and thus any interpreter for System F is not self-recursive.

This then extends to Turing-complete languages: JavaScript, Python, Ruby, etc. Any interpreter you run is utilizing functions more powerful than primitive recursion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.