# Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\}$ is not recognizable, which does not seem to help in this case...

• I'd try a few attempts exploiting the s-m-n theorem and the 2nd recursion theorem to build quine-like TMs. It might lead to a useful m-reduction. (Why is this marked complexity-theory ?) – chi Dec 16 '15 at 20:51

Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.
• If I understand correctly: If S is decidable, there is a decider for $S$ denoted as $H$. To obtain a contradiction, we construct a TM $B$ such that on input $w$, $B$ ignores $w$ and obtains a description of itself $\langle B\rangle$. Then $B$ run $H$ on $\langle B\rangle$. For the output, $B$ reject if $H(\langle B\rangle)$ accept and accept if $H(\langle B\rangle)$ reject. So the output of $B$ is always in contradiction with itself? – Yuanchu Dang Dec 17 '15 at 2:19