Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive

Question

Question: Let $$S = \{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape} \}.$$ Show that $S$ is r.e. (Turing acceptable) but not recursive (decidable).

I'm bit confused about this question, I'm not even sure how exactly should I start an approach to it. As I study from Sipser's book, in general when we prove a language is undeciable, we use contradiction to show that if $S$ is decidable, then by doing some trick, $A_{\text{TM}}$ is also decidable but it's not. Thus, $S$ is not decidable. However, this question also asked to show $S$ is acceptable. I'm thinking if we show that $S$ is undecidable, it's sufficient to see that $S$ is acceptable?(I'm totally not sure) Any suggestion?

Answer 1

First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the third cell, we can do the simulation without looping. Thus, if TM $R$ exists, we can decide $A_{TM}$, but we know that $A_{TM}$ is undicidable, by contradiction, we can conclude that $R$ doesn't exist. Hence, $S_3$ is undecidable.

Let's assume $S_3$ is decidable so we can obtain contradiction by having TM $R$ decides $S_3$, and construct TM $M'$ to decide $A_{TM}$ as follows.

$M'$ = $``$On input $\big \langle M, 3 \big \rangle$:

1. Run TM $R$ on input $\big \langle M, 3 \big \rangle$.
2. If $R$ rejects, $reject$.
3. If $R$ accepts, simulate $M$ to write symbol $``3"$ on the third cell of its tape.
4. If $M$ has accepted, $accept$; if $M$ has rejected, $reject$."

Clearly, if $R$ decides $S_3$, then $M'$ decides $A_{TM}$. However, since $A_{TM}$ is undecidable, so we know $R$ doesn't exist and hence $S_3$ must be undecidable.