Skip to main content
Tweeted twitter.com/StackCompSci/status/802936513809903616
Damnit, Alan Turing deserves a capital letter.
Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

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

Source Link

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?