# 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: 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?

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.