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.

  • $\begingroup$ Please correct the author's name. Practice heeding How to reference material written by others. $\endgroup$
    – greybeard
    Jul 11, 2022 at 18:42
  • $\begingroup$ @greybeard let me know if I need to make any further changes. $\endgroup$ Jul 13, 2022 at 1:43
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Jul 13, 2022 at 4:32


Your Answer

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