I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?
There are different definitions of computability.
- A function is computable if there is a terminating Turing machine which computes the result.
- A function is computable if there is a µ recursive function which computes the result.
- A function is computable if there is a lambda expression in untyped lambda calculus whose beta reduction terminates and which computes the result of the function.
All these definitions are pretty formal (i.e. "execution" can be done by a machine). The definitions have been invented at the beginning of the 20th century in order to find a precise definition for the predicate "can be computed mechanically".
It can be proved that all these definitions are equivalent. E.g. for any terminating Turing machine there exists a µ recursive function which calculates the same result. For any µ recursive function there exists a terminating Turing machine which calculates the same result. These proofs can be found in recursion theory. The proofs are general. I.e. they apply to all Turing computable functions, to all µ recursive computable functions etc.
Since the primitive recursive functions are a subset of µ-recursive functions they are clearly computable in the sense of µ recursive functions. Since all µ recursive functions are Turing computable, clearly all primitive recursive functions are Turing computable as well.