What are the applications of primitive recursive functions?

Question

So I was studying primitive recursive functions and I thought what could be their possible. Is the property of not having infinite loops used somewhere? Because since they do not represent the set of all computable problems,what is their use exactly?

Answer 1

The thing that is actually important is being a total computable function, which is to say that there is an algorithm that can compute any value of the function in finite time.

The primitive recursive function are an important, but proper, subset of the total computable functions. Some reasons for this include:

1. It is relatively easy to convince oneself that every primitive recursive function is total computable, even if you're being skeptical about high-powered proof methods that may be needed to prove other algorithms total (such as inifinitary set theory).

2. It is easy to prove things about the primitive recursive functions, because their definition gives rise to a structural induction principle.

3. Most functions that we need to consider in computability theory, proof theory, etc. are in fact primitive recursive, which means that we don't need to go beyond primitive recursion and look for proof techniques that work for more general total computable functions.

Answer 2

If you know that some piece of code calculates a primitive recursive function, then you know that it does not have an infinite loop. This is an important property that you don't have for computable functions in general, because in most cases, you don't want an infinite loop.

In practice, an overwhelming fraction of all code written computes primitive recursive functions. As a programmer, when you write a loop, how do you convince yourself it's not an infinite loop? Almost always, it boils down to the fact that you have an upper bound for the number of iterations in advance, and thus you have a primitive recursive function, and thus there is no infinite loop.