# Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$

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?

• Try using the recursion theorem. Nov 27, 2016 at 10:54
• @YuvalFilmus I haven't learned about this in my lecture. Would you mind explaining? I believe however that there should also be a solution without the theorem. Nov 27, 2016 at 11:06
• Perhaps your textbook contains some information on the recursion theorem. I find it somewhat hard to believe that you can avoid ideas similar to the recursion theorem. Nov 27, 2016 at 11:57

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.