# Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $$A_{ETM}$$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization argument not work:

Assume $$A_{ETM}$$ is decidable, and $$R$$ decides $$A_{ETM}$$. Then, $$R$$ accepts $$\langle M, w \rangle$$ when ETM $$M$$ accepts $$w$$. Let $$D$$ be an ETM that accepts exactly when $$M$$ does not accept $$w$$. Then, $$D$$ rejects $$\langle D \rangle$$ when $$D$$ accepts $$\langle D \rangle$$, a contradiction.

Why does this not work?

Alternatively, if $$A_{ETM}$$ is decidable, why is $$E_{ETM}$$ undecidable? The conventional contradiction argument would not work in that case, and I don't know how to reduce it any other way.

• I have point out a flaw in your proof (the part that is in bold). What is $M$ so that you can define $D$ like that. – Thinh D. Nguyen Oct 18 '18 at 12:24
• Hmm, I'm not sure what you mean - $M$ is an ETM such that $L(M)$ is decidable? I don't see how that would help, since the conventional $A_{TM}$ argument works for all TMs $M$? – Barış Ekim Oct 18 '18 at 12:47
• Shouldn't the last step be: $D$ accepts $\langle D \rangle$ when $M$ does not accept $\langle D \rangle$? Why is that a contradiction? Why was $R$ never used? I can't see any diagonalization argument above. – chi Oct 18 '18 at 13:53

So, an ETM can only accept some context-sensitive language. As a result, $$A_{ETM}$$ is decidable.
Where is the source that says $$E_{ETM}$$ is undecidable?
• Thanks for the response! If for any ETM $M$, $L(M)$ is a CSL, then we can say $E_{ETM}$ is undecidable, since $E_{LBA}$ is undecidable, can't we? – Barış Ekim Oct 18 '18 at 15:00
• No, because $E_{ETM}$ is a sub-problem of $E_{LBA}$. It might be easier. – Thinh D. Nguyen Oct 18 '18 at 15:02