patternMinor
Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?
Viewed 0 times
whylangleranglerecognizableturingnot
Problem
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$?
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$?
Solution
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$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.
Context
StackExchange Computer Science Q#7469, answer score: 5
Revisions (0)
No revisions yet.