HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#78142, answer score: 3

Revisions (0)

No revisions yet.