snippetMinor
Is there a "natural" example of a total, computable but non-primitive recursive function?
Viewed 0 times
totalcomputablenonexamplebutfunctionprimitiverecursivenaturalthere
Problem
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?
Solution
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.
This then extends to Turing-complete languages: JavaScript, Python, Ruby, etc. Any interpreter you run is utilizing functions more powerful than primitive recursion.
Context
StackExchange Computer Science Q#78142, answer score: 3
Revisions (0)
No revisions yet.