patternMinor
Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$
Viewed 0 times
lefttheallwithlanglerangledecidemachinesturingset
Problem
How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?
When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.
Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.
Is there an easy reduction to a known undecidable language?
When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.
Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.
Is there an easy reduction to a known undecidable language?
Solution
The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.
Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.
Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.
Context
StackExchange Computer Science Q#66560, answer score: 4
Revisions (0)
No revisions yet.