2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.