1
$\begingroup$

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!

| cite | improve this question | |
$\endgroup$
  • $\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$ – Thinh D. Nguyen Oct 18 '18 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$ – Barış Ekim Oct 18 '18 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 Oct 18 '18 at 13:53
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Barış Ekim Oct 18 '18 at 15:00
  • $\begingroup$ No, because $E_{ETM}$ is a sub-problem of $E_{LBA}$. It might be easier. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 15:02

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.