# show that neither $S$ nor $\overline{S}$ is turing recognizable

Let $$S = \{\langle M\rangle | M \text{ is a TM and } L(M) = \{ \langle M\rangle\}\}$$. Prove that neither $$S$$ nor $$\overline{S}$$ is Turing-recognizable.

I think the statement can be proved via a contradiction. Suppose $$S$$ is Turing recognizable and let $$M$$ be a TM recognizing it. Then M accepts all strings $$\langle T\rangle$$ where $$T$$ is a TM and $$L(T) = \{\langle T\rangle\}$$. By the recursion theorem, for any Turing machine $$T,$$ there exists a Turing machine $$Q$$ so that $$Q(\epsilon)$$ behaves the same way as $$T(\langle Q\rangle)$$. One can use the recursion theorem to justify why a Turing machine can get its own "source code." Perhaps one way to show the desired result would be to use a mapping reduction from a known non Turing-recognizable language, like $$E_{TM} := \{\langle M\rangle : L(M) = \emptyset\}$$ or $$EQ_{TM} := \{\langle M_1, M_2\rangle : L(M_1) = L(M_2)\}$$. But I can't think of the details for this.

• Please correct the author's name. Practice heeding How to reference material written by others. Jul 11, 2022 at 18:42
• @greybeard let me know if I need to make any further changes. Jul 13, 2022 at 1:43
• The name is Sipser. In case of locating contents by page number be sure to include the edition/ISBN. It is somewhat common to make the title stand out. In markdown, enclosing in * should render italics: Sipser, Michael: Introduction to the Theory of Computation. Jul 13, 2022 at 4:32