2. The second tape is used to store the stack.

3, The third tape is the output tape. Every time a symbol is popped from the stack, it must be written on the output tape, following all previously written symbols.

The Turing machine is required to start with an empty stack and implement the sequence of push and pop operations, as specified on the input, reading from left to right. If the input causes the TM to try to pop and empty stack, then it must halt in a special error state . If the entire input leaves the stack empty at the end, then the input is accepted by going to the final state q/. Describe the transition fimction of the TM informally but clearly. Also, give a summary of the purpose of each state you use.

Exercise 8.4.8: In Fig. 8.17 we saw an example of the general simulation of a fc-tape TM by a one-tape TM.

* a) Suppose this technique is used to simulate a 5-tape TM that had a tape

alphabet of seven symbols. How many tape symbols would the one-tape TM have?

* b) An alternative way to simulate к tapes by one is to use a (fc 4- l)st track

to hold the head positions of all fc tapes, wliile the first к tracks simulate the к tapes in the obvious manner. Note that in the {k + l)st track, we must be careful to distinguish among the tape heads and to allow for the possibility that two or more heads are at the same cell. Does this method reduce the number of tape symbols needed for the one-tape TM?

c) Another way to simulate к tapes by 1 is to avoid storing the head positions altogether. Rather, a (fc -1- l)st track is used only to mark one cell of the tape. At all times, each simulated tape is positioned on its track so the head is at the marked cell. If the fe-tape TM moves the head of tape i, then the simulating one-tape TM slides the entire nonblank contents of the ith track one cell in the opposite direction, so the marked cell continues to hold the cell scanned by the ith tape head of the fc-tape TM. Does this method help reduce the number of tape symbols of the one-tape TM!? Does it have any drawbacks compared with the other methods discussed?

! Exercise 8.4.9: A k-head Turing machine has fc heads reading cells of one tape. A move of this TM depends on the state and on the symbol scanned by each head. In one move, the TM can change state, write a new symbol on the cell scanned by each head, and can move each head left, right, or keep it stationary. Since several heads may be scanning the same cell, we assume the heads are numbered 1 through fc, and the symbol written by the highest numbered head scanning a given cell is the one that actually gets written there. Prove that the languages accepted by fe-head Turing machines are the same as those accepted by ordinary TMs.

!! Exercise 8.4.10: A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in the start state, as usual. Acceptance is by entering a final state, also as usual. Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary TMs.

8,5 Restricted Turing Machines

We have seen seeming generalizations of the Turing machine that do not add any language-recognizing power. Now, we shall consider some examples of apparent restrictions on the TM that also give exactly the same language-recognizing power. Our first restriction is minor but useful in a number of constructions to be seen later: we replace the TM tape that is infinite in both directions by a tape that is infinite oidy to the right. We also forbid this restricted TM to print a blank as the replacement tape symbol. The value of these restrictions is that we can assume IDs consist of only nonblank symbols, and that they always begin at the left end of the input.

We then explore certain kinds of multitape Turing machines that are generalized pushdown automata. First, we restrict the tapes of the TM to behave like stacks. Then, we further restrict the tapes to be counters, that is, they can only represent one integer, and the T.M can only distinguish a count of 0 from any nonzero count. The impact of this discussion is that there are several very simple kinds of automata that have the full power of any computer. Moreover, undecidable problems about Turing machines, which we see in Chapter 9, apply as well to these simple machines.

8.5.1 Turing Machines With Semi-infinite Tapes

Wile we have allowed the tape head of a Turing machine to move either left or right from its initial position, it is only necessary that the TMs head be allowed to move within the positions at and to the right of the initial head position. In fact, we can assume the tape is semi-infinite, that is, there are no cells to the left of the initial head position. In the next theorem, we shall give a construction that shows a TM with a semi-infinite tape can simulate one whose tape is, like our original TM model, infinite in both directions.

The trick behind the construction is to use two tracks on the semi-infiiute tape. The upper track represents the cells of the original TM that are at or to the right of the initial head position. The lower track represents the positions left of the initial position, but in reverse order. The exact arrangement is suggested in Fig, S,19. The upper track represents cells Xo,Xi,... , where Xq is the initial position of the head; Xi,X2, and so on, are the cells to its right. Cells X i,X 2, and so on, represent cells to the left of the initial position. Notice the * on the leftmost cells bottom track. This symbol serves as an

endraarker and prevents the head of the semi-infinite TM from accidentally falling off the left end of the tape.

Figure 8.19: A semi-infinite tape can simulate a two-way infinite tape

We shall make one more restriction to our Turing machine: it never writes a blank, This simple restriction, coupled with the restriction that the tape is only semi-infinite means that the tape is at all times a prefix of nonblank symbols followed by an infinity of blanks. Further, the sequence of nonblanks always begins at the initial tape position. We shall see in Theorem 9.19, and again in Theorem 10.9, how useful it is to assume IDs have this form.

Theorem 8.12: Every language accepted by a TM M2 is also accepted by a TM Ml with the following restrictions:

1. M] s head never moves left of its initial position.

2, Ml never writes a blank.

PROOF: Condition (2) is quite easy. Create a new tape symbol B that functions as a blemk, but is not the blank B. That is:

a) If M2 has a rule diQjX) = {p,B,D), change this rule to 62(4, X) ~ (p,B,D).

b) Then, let 2(9, B) be the same as 2(9, B), for every state q. Condition (1) requires more effort. Let

M2 - {(32, S,r2,52,92,,2) be the TM M3 as modified above, so it never writes the blank B. Construct Ml = X {B},ruSuqo,[B,B],F,)

where:

(5i: The states of Mi are {qo,qi} U {Q2 x. {U, L}). That is, the states of Mi are the initial state qo another state qi, and all the states of M2 with a second data component that is either U ov L (upper or lower). The second component tells us whether the upper or lower track, as in Fig, 8.19 is being scanned by M2. Put another way, U means the head of M2 is at or to the right of its initial position, and L means it is to the left of that position.