The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998

Detailed Solutions

Chapter 4, Problem 6

We need to show that a (deterministic) Turing machine that has three choices for its head movement (stay, move left, or move right) can be simulated by a (deterministic) Turing machine that has only two choices. The simulation is really very simple: we use extra control states and move the head left, then back to the right to simulate the absence of move. Thus, if the augmented Turning machine has a transition of the type delta(q_i,a)=(q_j,b,-) where the dash denotes that the head stays put, our simulation uses the two transitions delta(q_i,a)=([q_i,a],b,L) delta([q_i,a],c)=(q_j,c,R) for all c in Sigma while transitions that do move the head are the same in both machines. The notation [q_i,a] denotes a new state for each pair q_i and a such that the augmented Turing machine makes a transition with stationary head when in state q_i reading input a. Our simulation runs in at most twice the number of steps of the original Turing machine, with exactly the same tape contents are all steps; if the Turing machine we are simulating uses an alphabet of k characters and has q control states, then our simulating machine has up to (k+1)q control states.