3
$\begingroup$

I cannot quite feel the difference between two models.

The first one is read-only Turing machine which is basically the same as Turing machine with write protected input. See this question for example: Single-tape Turing Machines with write-protected input recognize only Regular Languages

It was said that it indeed recognizes only regular languages because there is no way to copy an input without rewriting it somewhere.

And there are non-erasing Turing machines that (in binary representation) cannot overwrite $1$ with $0$. This is equivalent to full power Turing machine as it was explained here Non-erasing Turing machines and loss of generality and in the paper http://arxiv.org/pdf/1304.0053

But what is the difference? We still cannot copy some strings like $1111$ due to lack of overwriting power.

So why it is weak when we cannot write only on input but strong when we cannot overwrite $1$ with $0$ everywhere? Why we can encode strings in one case but not the other?

$\endgroup$
  • 1
    $\begingroup$ Non-erasing Turing machines can still write non-blanks. BTW: a blank and a 0 that is part of a binary input string are not the same thing. $\endgroup$ – reinierpost Dec 15 '15 at 22:22
  • $\begingroup$ @reinierpost, 0 and blank are pretty much the same as it is in arxiv paper. You can write non-blanks, but when you have only one non-blank symbol there are not as many options. And still there is a difference. $\endgroup$ – sas Dec 15 '15 at 22:56
  • $\begingroup$ Yes, the difference is, as the paper explains, that the input is not interpreted as binary but as unary. $\endgroup$ – reinierpost Dec 16 '15 at 13:22
5
$\begingroup$

A non-erasing TM has a tape alphabet $\{0,1\}$ where $0$ acts as blank. The $0$ can be rewritten into $1$, but that symbol cannot be "erased", i.e., written back into $0$.

This restriction seems to be equivalent to symbols that can be rewritten only a finite number of times. TM's do have the capability of interpreting a finite segment of tape as one symbol. Then $0000$ can be rewritten into $0001$ then into $0011$, into $0111$, into $1111$. A little modulo counting interprets these segments as $0,1,0,1,0$.

Recall that a TM is equivalent to a finite state machine that has a queue as basic datastructure. It can read and delete on one side, and write on the other. To see that this is equivalent to a TM a rotation trick is done: the queue holds the tape in a circular fashion, but can only move on the tape in one direction. To move into the other direction just move all the way.

This rotation trick can also be done on the tape of a TM, and needs only finite rewrites on the same position. One needs to be able to rewrite the tape from $Ax$ into say $xB$ where $A,B$ are symbols and $x$ is a string.

$\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.