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?

  • $\begingroup$ By definition, arguably; they are clearly a subset of the $\mu$-recursive functions which are Turing-equivalent. $\endgroup$ – Raphael Mar 28 '16 at 18:18
  • $\begingroup$ And how do you prove they are Turing-equivalent? One direction uses exactly this result. $\endgroup$ – Yuval Filmus Mar 28 '16 at 18:24

You prove it by structural induction over the definition of primitive recursive functions. The definition of computable is: a function is computable if it is computable by a Turing machine. There are many other equivalent definitions.

  • $\begingroup$ So do I need to provide a definition of TM that computes those functions? $\endgroup$ – user48566 Mar 28 '16 at 17:53
  • $\begingroup$ No, you use the Church-Turing thesis to just present an informal algorithm. You can find many examples in any textbook on computability theory (aka recursion theory). $\endgroup$ – Yuval Filmus Mar 28 '16 at 17:55
  • $\begingroup$ There is no need to invoke the CTT here, since we can easily have a true proof. $\endgroup$ – Raphael Mar 28 '16 at 18:18

There are different definitions of computability.

  1. A function is computable if there is a terminating Turing machine which computes the result.
  2. A function is computable if there is a µ recursive function which computes the result.
  3. 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.
  4. ...

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.

  • $\begingroup$ OK but doesn't this beg the question? How would you prove that the $\mu$-recursive functions are computable? $\endgroup$ – David Richerby Mar 29 '16 at 1:14

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.