186 TURING MACHINES
Then, A41 simulates each move of A4 as follows: We assume that after
each simulation step, A41 is scanning a tape cell such that all the symbols X
appear to the left of that cell. To begin the simulation, A&r moves from right
to left scanning all groups to look for the symbols X and the symbols in r‘
that appear at the top of X’s. After it finds all X’s, it has also collected all
the tape symbols that are currently scanned by the tape heads of A.4 (these
tape symbols are remembered in the state of A&). Next, A41 moves back from
left to right and looks for the symbols X again. This time, for each symbol
X, A41 properly simulates the action of A4 on that tape. Specifically, it writes
over the symbol of the first track of the cell where the second track has an X,
and moves the symbol X to the right or to the left or keep it where it is. The
simulation is done when actions on all k tapes are taken care of. Note that,
by then, all the symbols X appear to the left of the tape head of A&
At the end, when A4 reaches a halting configuration, Mr erases all symbols
in all groups except the output group, converts the tape into a single track
form with outputs only, and leaves its head scanning the cell which contains
X in the second track of the output group.
In the following, we present a more detailed description of how machine A41
simulates one move of A&. The rest of the machine &?I is left as an exercise.
Assume that A4 = (Q, C, I’& s) is a three-tape DTM. Also assume that
A& has already set up the tape in the six-track form, and that its tape head
is scanning a cell to the right of all symbols X. We divide the simulation of
one move of A4 into two stages. In the first stage, Mi moves from right to
left to collect the tape symbols currently scanned by AL In the second stage,
A41 moves from left to right to simulate the writing and moving of the tape
heads of A&. In the first stage, A41 will use the following set of states:
{q x,y,x 1 q E Q, g, ~7 x E r u {?} },
where? is a symbol not in I’. A subscript IX: E I? indicates that the tape symbol
x has been collected, and the subscript? indicates that this tape symbol isstill unknown. For instance, q?b? denotes that M is currently in state q, and
its second tape head is reading symbol b, and Mr is yet to find out what the
other two tape heads are reading.
The instructions of A41 for the first stage can be described as follows, be-ginning with state q???. (In the following, unless otherwise specified, each
instruction applies to all 2, y, x E I? U {?} and all a, b, c E I.)61 (%yz, [a, B, b, B, 5 BI) = (qzyz, [a, B, b> B, c, Bl, L)
if x =? or y =? or x =?,S1 (qTyz, [a, X, b, B, c, B]) = (qayz, [a, x, b, 6 c, B] I L) 7
J (a^1 x?z,[a,B,Gcc31) = (qxbz,[a,B,b,X,c,Bl,L),
(5 (q 1 xy?, [0404cGf1) = (qxyc, [a, B, b7 4 c> Xl> L)J