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

Question

This question is chapter 5, problem 33 (5.33) from Michael Sisper's Introduction to the Theory of Computation:

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.

Answer 1

Here's a reduction $\overline{A_\mathsf{TM}} \leq_\mathrm{m} S$:

Let the mapping be $f(\langle M, w\rangle) = R_{M,w}$ where
$R_{M,w}$ = "On input $x$,

1. Get $\langle R_{M,w}\rangle$ from the recursion theorem.
2. If $x = \langle R_{M,w}\rangle$, then accept.
3. Run $M$ on $w$. If $M$ accepts, then accept. If $M$ halts and rejects, then reject."

Then $L(R_{m,w}) = \Sigma^*$ if $M$ accepts $w$ and $\{\langle R_{m,w}\rangle\}$ otherwise.

Here's a reduction $\overline{A_\mathsf{TM}} \leq_\mathrm{m} \overline{S}$:

Let the mapping be $f'(\langle M, w\rangle) = R'_{M,w}$ where
$R'_{M,w}$ = "On input $x$,

1. Run $M$ on $w$. If $M$ halts and rejects, then reject. If $M$ halts and accepts, continue to step 2.
2. Get $\langle R'_{M,w}\rangle$ from the recursion theorem.
3. If $x = \langle R'_{M,w}\rangle$, then accept. Otherwise, reject."

Then $L(R'_{m,w}) = \{\langle R_{m,w}\rangle\}$ if $M$ accepts $w$ and $\emptyset$ otherwise.