Problem Detail: Is the set $S$ = $lbrace M mid M text{ is a Turing machine and }L(M)=lbrace langle Mranglerbracerbrace$ empty? In other words is there a Turing machine $M$ that only accepts its own encoding? What about a Turing machine that rejects only its own encoding?
Asked By : A. H.
Answered By : Vor
The answer is yes. See Kleene’s second recursion theorem: for any partial recursive function $Q(x,y)$ there is an index $p$ such that $varphi_p simeq lambda y.Q(p,y)$. Suppose that $M$ is a Turing machine that on input $langle x,y rangle$ accepts if and only if $x=y$; then, by the above theorem, exists $M’$ such that $M'(langle y rangle) = M(langle M’ , y rangle)$ and we have $L(M’) = { langle M’ rangle }$. P.S. you can find a very clear proof of the recursion theorem in Chapter 6 of the M. Sipser’s book “Introduction to the theory of computation”.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18989
