6.4 Nondeterministic Turing Machines 307
such an algorithm a guess-and-verify algorithm. We will see more examples
of such algorithms in Section 7.1.
In the above, we have defined one-tape NTM’s. Multi-tape NTM’s can be
defined in a similar way. That is, a k-tape NTM operates just like a i&tape
DTM, except that at one step, it may have more than one choice of next
moves. We leave the detail of the definition to the reader.
Are NTM’s more powerful than DTM’s? The answer is no, in the sense that
the class of languages accepted by NTM’s is exactly the class of r.e. languages.
This result could be considered as another support for the Church-Turing
Thesis, even though we, in general, do not consider the NTM as a reasoszable
computatonal model, since there does not seem to be any physical devices
that can be used to build such a machine.
Theorem 6.23 Every set accepted by an NTM is an r.e. set.
Proof. For simplicity, we consider only one-tape NTM’s. The proof for the
multi-tape NTM’s is similar.
Assume that A& = (Q, C, I’, 8, ~0) is a one-tape NTM. Note that S is map-
ping from Q x I’ to 2 QxrxPW. Let Ic be the maximum size of sets S(q, a)
over all (4, a) E Q x I?; that is, at each move, M has at most Ic choices of
the next moves. Let r)l,r)z, l l l , r)k be Ic new symbols which are not in I?. We
construct a three-tape DTM M to simulate M as follows:
(1) M keeps a string y over the alphabet {ql,772,... , qk} in the second
tape. Initially, y = VI.
(2) M copies the input II: from the first tape (the input tape) to the third
tape and simulates M on input z on the third tape. During the simu-
lation, it moves its tape head of the second tape toward right at each
move. In other words, when M is simulating the jth move of M on x:,
it is also reading the jth symbol of the string y in the second tape. If
the jth symbol of y is qr, then M follows the rth choice for the next
move of M (and if M has less than T choices for the next move, it fol-
lows the first choice). If IyI < j (i.e., the head of the second tape is
scanning a blank symbol), then go to step (3). The machine M* halts
if the simulation halts in state h within Iyj moves.
(3) Increment y of the second tape by one; that is, replace y by the next
string over {~1,7;72,... , qk}, in the lexicographic ordering. Then, go back
to step (2).
We check that if there is an accepting computation path of M on x: of length
m, then this computation path corresponds to a sequence (il, i2,... , &J of
integers in { 1,2,... , k}, in the sense that to get this path, the rth move of M
follows the i,th next-move among all choices. Therefore, M will halt when
it reaches the string y = vi1qi2 l l l vi, at the second tape. Conversely, it is
obvious that M halts only when it finds an accepting computation path of
M. Thus, we have L(M) = L(M*). cl