the OM, while the other m tracks are used to show the position of OM’s tape
heads.
SM will simulate each move of the OM by scanning and updating its active
area.
5. This exercise shows that a queue machine is equivalent to a standard Turing
machine and that therefore a queue is a more powerful storage device than a
stack. To simulate a standard TM by a queue machine, we can, for example,
keep the right side of the OM in the front of the queue, the left side in the
back.
A right move is easy, as we just remove the front symbol in the queue and
place something in the back. A left move, however, goes against the grain,
so the queue contents have to be circulated several times to get everything
in the right place. It helps to use additional markers Y and Z to denote
boundaries. For example, to simulate
we carry out the following steps.
(i) Remove c from the front and add zY to the back.
(ii) Circulate contents to get bzY defgxa.
(iii) Add Z to the back, then circulate, discarding Y and Z as they come to
heads.
SM will simulate each move of the OM by scanning and updating its active
area.
5. This exercise shows that a queue machine is equivalent to a standard Turing
machine and that therefore a queue is a more powerful storage device than a
stack. To simulate a standard TM by a queue machine, we can, for example,
keep the right side of the OM in the front of the queue, the left side in the
back.
A right move is easy, as we just remove the front symbol in the queue and
place something in the back. A left move, however, goes against the grain,
so the queue contents have to be circulated several times to get everything
in the right place. It helps to use additional markers Y and Z to denote
boundaries. For example, to simulate
we carry out the following steps.
(i) Remove c from the front and add zY to the back.
(ii) Circulate contents to get bzY defgxa.
(iii) Add Z to the back, then circulate, discarding Y and Z as they come to