4
$\begingroup$

I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles for the fact that one single-head tape doesn't suffice for this problem and the simulation should be done using two single-head tapes, but I haven't been able to present an accurate simulation of two-head TM using these single-head tapes. Are there any thoughts on how to do so? Thanks,

$\endgroup$

migrated from cstheory.stackexchange.com Sep 13 '12 at 2:13

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ I think the terminology is confusing here. As I understand it, you want to simulate one-tape two-head TMs with one-tape one-head TMs, but think you need two-tape two-head machines. Correct? $\endgroup$ – Raphael Sep 13 '12 at 6:44
  • $\begingroup$ Unhelpful answer: as it's unlikely that two-head machines are more powerful than Turing machines, of course there is an equivalent TM. I am not sure whether this implies that there has to be a computable simulation, though. $\endgroup$ – Raphael Sep 13 '12 at 6:46
2
$\begingroup$

Two heads on a single tape are more powerful (in real time) than two single heads on two distinct tapes.

See T. Jiang, J.I. Seiferas and P.M.B. Vitanyi, 1994, "Two Heads Are Better than Two Tapes"

EDIT: I just read the proof and it is not trivial (and I didn't read/understand the details :-):

The language $L = \{ x2x' | x \in \{ 0,1 \}^* $ and $x'$ is a prefix of $x$ $\}$ can be easily recognized by a two-head single tape TM in real time: one of the two heads stays on the beginning of the input, the second moves right and as soon as it reads the 2 both move right and check whether $x'$ is a prefix of $x$.

But $L$ cannot be recognized by a two single-head tapes TM in real time. In a TM with two single-head tapes one of the two tapes is empty and trivially if the first head scans the input while the other copies it, when the 2 is read, the prefix of $x$ is far from both heads.

Hence the prefix(es) of $x$ should be made "quickly" available at every time using a so called "holographic" representation (see fig. 1 of the paper). But if $x$ is incompressible this cannot be achieved and when it is time to check the prefix one of the two heads must move too far from its current position (the number of moves cannot be bound by a constant).

$\endgroup$
  • 1
    $\begingroup$ Can you outline the essential argument? $\endgroup$ – Raphael Sep 13 '12 at 7:28
  • $\begingroup$ Hm, I wonder how that relates to the question, which asks for an "on-line simulation". It seems to me that copying the input, resetting to the beginning, and them simulating the original machine works. Is there some meaning behind "on-line" I am not getting? $\endgroup$ – Raphael Sep 15 '12 at 13:12
  • $\begingroup$ @Raphael: you are right, it is not related (real-time is a much tighter simulation) :( ... I'll fix it; the proof that the general online simulation of a two heads TM can be done with a two single-head tapes is easier $\endgroup$ – Vor Sep 15 '12 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy