Simulating a TM with a 2-head, right moving TM

Question

Is it possible to simulate a regular Turing Machine with a TM with the following specs?

1. There are two heads, one of which can read, one of which can write
2. Both heads can only move right
3. When a head reads (or it writes) it moves right

I know it's possible to simulate a TM that only moves right. But, is it possible to simulate the left moves as well?

Answer 1

Yes you can simulate a standard Turing machine, indeed you can easily simulate a Tag System which is Turing complete (and can simulate a Turing machine with only a polynomial-time slowdown).

Informally to simulate a k-tag system, you keep the write head at the end of the tape (on the first blank symbol) and use internal states to store the production rules; with the read head you can read k symbols, and append the symbols of the corresponding production rule at the end of the tape.

For example if you have a 2-tag system with the following production:

a --> aab

and the tape is:

a b a b c a b c _
^               ^
Read            Write

you can read the first two symbols and apply the production:

a b a b c a b c a a b _
    ^                 ^
    Read              Write

Furthermore it is also easy to see how a k-Tag system can simulate a Turing machine; a hint: use a special symbol to mark the position of the head, and just rewrite (with one symbol of delay) on the right what you read with the read head but on the "new copy" change the symbol on the right of the head marker according to the transition table of the simulated TM and also change the head marker position one step left or right (and at every "copy cycle" write also two "empty spaces" to allow the expansion of the tape); use internal states to keep track of the copy phase and of the current state of the simulated TM.

For example if you use # to mark the head position and one transition is:

q1, read a -> q2, write b, move left


a c # a a b c a b c _ a _
    ^RH               ^WH (q1 and c are buffered in the internal states)                

a c # a a b c a b c _ a _
      ^RH               ^WH (here the "simulated" TM is on symbol "a"
in state q1 and we can apply the transition above)

a c # a a b c a b c _ a # c b _
        ^RH                   ^WH (q2 is buffered in the internal state)                

continue with the copy and start another "cycle":

a c # a a b c a b c _ a # c b a b c a b c _
                    ^RH                   ^WH                 

... let me know if you need more hints.