2
$\begingroup$

A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I'm trying to understand whether there is loss of generality because of this restriction.

My guess is that there is no loss of generality, because the restriction above merely restricts replacing characters with blanks, but we can just as easily replace them with some other symbol and construct any rules that might have used blanks to use the new symbol. I think that's too simple a solution though.

Can anyone give me any insight as to how to show whether or not generality is lost in the special case of non-erasing Turing machines?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Why do you think that solution is too simple? What's wrong with simple solutions? If you're not sure whether your solution is correct, try writing a careful proof. $\endgroup$ – D.W.♦ Apr 20 '15 at 23:21
  • $\begingroup$ Without loss of generality is an expression that usually isn't taken apart. $\endgroup$ – Yuval Filmus Apr 21 '15 at 2:53
3
$\begingroup$

The purpose of the blank symbol is to differentiate the tape alphabet from the language alphabet. It is useful, typically, when you are trying to formulate a decision problem. From a more abstract point of view, as you clearly realize, a machine whose tape alphabet has at least two symbols is still exactly a Turing machine.

So you are erring towards generality, so to speak, not away from it.

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

Your definition of non-erasing Turing machine is "not the common one". Turlough Neary nicely summarizes early definitions and results for non-erasing Turing machines:

Non-erasing Turing machines are a restriction of Turing machines that are permitted to overwrite blank symbols only. Moore [Moo52] mentions that Shannon had proved that non-erasing Turing machines simulate Turing machines, however this result was never published. Shortly after, Shannon proved 2-symbol Turing machines universal, Wang [Wan57] proved 2-symbol non- erasing Turing machines universal. Later, Minsky [Min61] proved the same result as Wang using a different technique. Minsky proved 2-tape non- writing Turing machines were universal and showed 2-symbol non-erasing Turing machines simulate these non-writing machines.

So here it says "overwrite blank symbols only", while you wrote "cannot replace a symbol with a blank unless the symbol under the read head is a blank".

In general, it seems that being non-erasing is not a serious restriction, but the answer here has one reference with results that point in the opposite direction:

  1. John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.
|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.