Problem Solving in Automata, Languages, and Complexity

182 TURING MACHINES

Figure 4.12: The two tracks of a one-tape DTM.

will simulate the right-hand part of the two-way tape of A& that is, cells

cl, c2$3, l l l 7 and the top track will simulate the left-hand part of the two-

way tape of M, that is, cells Co, C-1, C-2,.... Note that the top track is

of the reverse direction of the left part of the two-way tape of M. That is,

the two tracks together are like the two-way tape of M folded around the

boundary between cells Co and Cr (see Figure 4.12).

In addition to this setting of the tape, machine M’ also has a larger state

set Q’. In particular, for each state q E Q, M’ has two corresponding states

q6 and qt to simulate the state q. Additional states are also used for other

purposes, and will be introduced later.

With this idea, the simulation is now straightforward. Let us call the cells

of the tape of M’, starting from the leftmost cell, CA, Ci, C&....

First, suppose that the input x to the machine M’ is stored in cells Ci,

C I CA, and the head is scanning the cell CA+l. Then, the machine M’

wZ?l &lace each symbol a in cells Ci, CL,... , Ck+r by the symbol [B, a], and
replace the symbol B in cell Ch by $. (W e write [B, a] to denote the symbol
whose top part is B and the bottom part is a.> It then goes back to cell CA+r

and changes its state to s6. At this point, the configuration of M’ is as follows:

(s6, $ [B, xl] [B, 223 l ’ ’ [B, xn] [B, B]),

where q is the ith symbol of IX: for i = 1,... , n. (Note: Cells CA+2, CA+3,...
still hold the original blank symbol B.)

Next, M’ begins to simulate machine M. If M’ is in a bottom state qb and

reads a symbol [a, b], then it simulates the action of J(q, b). For instance, if M

has an instruction 8(q, b) = (p, c, R), th en M’ has the following instructions:

S’(Qb, [a, b]) = (Pb, [a,C], R), for all a E I.

If M’ is in a top state qt and reads a symbol [a, b], then it simulates the action

of S(q, a). For instance, if M has an instruction 6(q, a> = (p, c, R), then M’

has the following instructions:

qqt, [a, b-j) = (Pt, [c, q, -Q, for all b E r*

Suppose that M’ moves into a cell which has not been split into two tracks

yet. It needs to split it. That is, for each q E Q, M’ has the following