Theorem 8.9: Every language accepted by a multitape TM is recursively enumerable.

PROOF: The proof is suggested by Fig. 8.17. Suppose language L is accepted by a fc-tape TM M. We simulate M with a one-tape TM N whose tape wc think of as having 2k tracks. Half these tracks hold the tapes of M, and the other half of the tracks each hold only a single marker that indicates where the head for the corresponding tape of M is currently located. Figure 8.17 assumes к = 2. The second and fourth tracks hold the contents of the first and second tapes of M, track 1 holds the position of the head of tape 1, and track 3 holds the position of the second tape head.

Figure 8.17: Simulation of a two-tape Turing machine by a one-tape Turing machine

To simulate a move of M, iVs head must visit the к head markers. So that N not get lost, it must remember how many head markers are to its left at all times; that count is stored as a component of As finite control. After visiting each head marker and storing the scanned symbol in a component of its finite control, knows what tape symbols are being scanned by each of Ms heads. Л also knows the state of M, which it stores in TVs own finite control. Thus, N knows what move M will make.

now revisits each of the head markers on its tape, changes the symbol in the track representing the corresponding tapes of M, and moves the head markers left or right, if necessary. Finally, Л changes the state of M as recorded in its own finite control. At this point, N has simulated one move of M.

We select as Nb acceptuig states all those states that record Ms state as one of the accepting states of M. Thus, whenever the simulated M accepts, N also accepts, and N does not accept otherwise. □

A Reminder About Finiteness

A common fallacy is to confuse a value that is finite at any time with a set of values that is finite. The many-tapes-to-one construction may help us appreciate the difference. In that construction, we used tracks on the tape to record the positions of the tape heads. Why could we not store these positions as integers in the finite control? Carelessly, one could argue that after n moves, the TM can have tape head positions that must be within n positions of original head positions, and so the head only has to store integers up to n.

The problem is that, while the positions are finite at any time, the complete set of positions possible at any time is infinite. If the state is to represent any head position, then there must be a data component of the state that has any integer as value. This component forces the set of states to be infinite, even if only a finite number of them can be used at any finite time. The definition of a Turing machine requires that the set of states be finite. Thus, it is not permissible to store a tape-head position in the finite control.

8.4.3 Running Time and the Many-Tapes-to-One Construction

Let us now introduce a concept that will become quite important later: the time complexity or running time of a Turing machine. We say the running time of TM M on input m is the number of steps that M makes before halting. If M doesnt halt on w, then the running time of M on ш is infinite. The time complexity of TM M is the function T{n) that is the maximum, over aU inputs w of length n, of the running time of M on ш. For Turing machines that do not halt on all inputs, T{n} may be infinite for some or even all n. However, we shall pay special attention to TMs that do halt on all inputs, and in particular, those that have a polynomial time complexity T{n)\ Section 10,1 initiates this study.

The construction of Theorem 8.9 seems clumsy. In fact, the constructed one-tape TM may take much more running time than the multitape TM. However, the amounts of time taken by the two Turing machines are commensurate in a weak sense: the one-tape TM takes time that is no more than the square of the time taken by the other. While squaring is not a very strong guarantee, it does preserve polynomial running time. We shall see in Chapter 10 that:

a) The difference between polynomial time and higher growth rates in running time is really the divide between what we can solve by computer and what is in practice not solvable.

b) Despite extensive research, the running time needed to solve many prob-

lems has not been resolved closer than to within some polynomial. Thus, the question of whether we are using a one-tape or multitape TM to solve the problem is not crucial when we examine the running time needed to solve a particular problem.

The argument that the running times of the one-tape and multitape TMs are within a square of each other is as follows.

Theorem 8.10: The time taken by the one-tape TM N of Theorem 8.9 to simulate n moves of the fc-tape TM M is 0{n).

PROOF: After n moves of M, the tape head markers cannot have separated by more than 2n cells. Thus, if N starts at the leftmost marker, it has to move no more than 2n cells right, to find all the head markers. It can then make an excursion leftward, changing the contents of the simulated tapes of M, and moving head markers left or right as needed. Doing so requires no more than 2n moves left, plus at most 2k moves to reverse direction and write a marker X in the cell to the right (in the case that a tape head of M moves right).

Thus, the number of moves by N needed to simulate one of the first n moves is no more than 4n + 2k. Since A: is a constant, independent of the number of moves simulated, this number of moves is 0{n). To simulate n moves requires no more than n times this amount, or O(n). □

8.4.4 Nondeterministic Turing Machines

A nondeterministic Taring machine {NTb4) differs from the deterministic variety we have been studying by having a transition function 5 such that for each state q and tape symbol X, 5{q,X) is a set of triples

{(д1,УьА), {q2,y2,D2),...Aqk,Yk,Dk)}

where к is any finite integer. The NTM can choose, at each step, any of the triples to be the next move. It cannot, however, pick a state from one, a tape symbol from another, and the direction from yet another.

The language accepted by an NTM M is defined in the expected manner, in analogy with the other nondetermhiistic devices, such as NFAs and PDAs, that we have studied. That is, M accepts an input w if there is any sequence of choices of move that leads from the initial ID with w as input, to an ID with an accepting state. The existence of other choices that do not lead to an accepting state is irrelevant, as it is for the NFA or PDA.

The NTMs accept no languages not accepted by a deterministic TM (or DTM if we need to emphasize that it is deterministic). The proof involves showing that for every NTM Мдг, we can construct a DTM Mq that explores the IDs that M can reach by any sequence of its choices. If Md finds one that has an accepting state, then Md enters an accepting state of its own. Md must be systematic, putting new IDs on a queue, rather than a stack, so that after some finite time Md has simulated all sequences of up to к moves of Mjv, for fc = 1,2,----