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.

Thanks in advance!

  • $\begingroup$ 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. $\endgroup$ Commented Oct 18, 2018 at 12:24
  • $\begingroup$ 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$? $\endgroup$ Commented Oct 18, 2018 at 12:47
  • $\begingroup$ 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. $\endgroup$
    – chi
    Commented Oct 18, 2018 at 13:53

1 Answer 1


An ETM (Erasing Turing machine) can be safely simulated due to its erasing-only nature.

It can only pass the right-end of the input to a finite limit or else would plunge off to infinity. Adding this to the input itself, we can conclude that the languages accepted by an ETM must be context-sensitive.

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?

  • $\begingroup$ 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? $\endgroup$ Commented Oct 18, 2018 at 15:00
  • $\begingroup$ No, because $E_{ETM}$ is a sub-problem of $E_{LBA}$. It might be easier. $\endgroup$ Commented Oct 18, 2018 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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