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$
$\endgroup$
2
-
$\begingroup$ By definition, arguably; they are clearly a subset of the $\mu$-recursive functions which are Turing-equivalent. $\endgroup$– RaphaelCommented Mar 28, 2016 at 18:18
-
$\begingroup$ And how do you prove they are Turing-equivalent? One direction uses exactly this result. $\endgroup$– Yuval FilmusCommented Mar 28, 2016 at 18:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Mar 28, 2016 at 17:43
-
$\begingroup$ So do I need to provide a definition of TM that computes those functions? $\endgroup$ Commented Mar 28, 2016 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$ Commented Mar 28, 2016 at 17:55
-
$\begingroup$ There is no need to invoke the CTT here, since we can easily have a true proof. $\endgroup$– RaphaelCommented Mar 28, 2016 at 18:18
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ OK but doesn't this beg the question? How would you prove that the $\mu$-recursive functions are computable? $\endgroup$ Commented Mar 29, 2016 at 1:14