Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?

, , No Comments
Problem Detail: 

In other words, $L$ is the language of Turing machines that recognize the language consisting of only themselves.

Why is $L$ not Turing-recognizable? $L$ is clearly not decidable by Rice's Theorem, but how do I go one step further and also prove that no machine can enumerate $L$?

Asked By : David Faux

Answered By : Yuval Filmus

Given a Turing machine $T$, use the recursion theorem to construct a Turing machine $T'$ that halts if its input $x$ is $\langle T' \rangle$, runs $T$ on $x$ if $x < \langle T' \rangle$, and runs $T$ on $x-1$ if $x > \langle T' \rangle$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7469

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback