Is it possible to simulate a regular Turing Machine with a TM with the following specs?There are two heads, one of which can read, one of which can writeBoth heads can only move rightWhen a head reads (or it writes) it moves rightI know it's possible to simulate a TM that only moves right. But, is it possible to simulate the left moves as well?
Simulating a TM with a 2-head, right moving TM
turing machines;turing completeness;simulation
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 --> aaband the tape is:a b a b c a b c _^               ^Read            Writeyou can read the first two symbols and apply the production:a b a b c a b c a a b _    ^                 ^    Read              WriteFurthermore 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 lefta 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 ain 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.