I saw this question and asked myself why the original problem is not solvable through diagonalization. Let $$L = \bigl\{\langle M \rangle \mid L(M) = \{\langle M\rangle\}\bigr\}$$ Take the complement $\overline{L}$. Suppose there is a Turing Machine $M$ which decides this language. We get the following two cases:

  • $\langle M \rangle \in \overline L \implies M \text{ accepts } \langle M \rangle \implies \langle M \rangle \notin \overline{L}$

  • $\langle M \rangle \notin \overline L \implies M \text{ does not accept } \langle M \rangle \implies \langle M \rangle \in \overline{L}$

Is this a valid proof?


1 Answer 1


If $\langle M \rangle \in \overline{L}$ then by definition of $M$, $M$ accepts $\langle M \rangle$, and so $\langle M \rangle \in L(M)$. This is not the same as $L(M) = \{\langle M \rangle\}$, and so we cannot conclude that $\langle M \rangle \in L$. It could be, for example, that $M$ accepts other inputs.

If $\langle M \rangle \notin \overline{L}$ then by definition of $M$, $M$ does not accept $\langle M \rangle$, and so $\langle M \rangle \notin L(M)$. In particular, $L(M) \neq \{ \langle M \rangle \}$, and so by definition of $L$, $\langle M \rangle \in \overline{L}$. So in this case we do get a contradiction.

The conclusion is that $\langle M \rangle \in \overline{L}$, and this does not directly lead to any contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.