The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start symbol followed by a blank followed by the input string followed by infinite blanks. The head is pointing at the blank just before the input string.

I think that this machine can perform any operation that an unrestricted Turing machine can because you can first copy the input string on the tape and then proceed with the operation. However, my friend pointed out that you cannot copy the string without overwriting it at some point.

Any thoughts?

  • 1
    $\begingroup$ It's not clear to me what your actual question is. "Any thoughts?" isn't really a question about computer science. $\endgroup$ Nov 28 '18 at 19:02
  • $\begingroup$ @DavidRicherby My question is regarding if the restricted Turing machine is as powerful as an unrestricted one. Also, if you can prove that you can copy the input string without overwriting it, that would mean the same. $\endgroup$ Nov 29 '18 at 0:42
  • 2
    $\begingroup$ cs.stackexchange.com/questions/22082/… $\endgroup$
    – xskxzr
    Nov 29 '18 at 10:32