- There are two heads, one of which can read, one of which can write
- Both heads can only move right
- 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?
Asked By : Alex Chumbley
Answered By : Vor
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19885 Ask a Question Download Related Notes/Documents