On-line simulation of a two-head tape Turing machine using single-head tape(s)

Question

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,

Answer 1

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).