Computability - Models of Computation: Exploring the Power of Computing - page 216

Read-Only Input Tape

Work Tape

Control

Unit

Enumeration Tape

0 1 1

Figure 5.7 A three-tape deterministic Turing machine that simulates a nondeterministic Turing
machine.

lating M ND . These sequences are generated in lexicographical order, that is, in the order
0, 1, 00, 01, 10, 11, 000, 001, ... . It is straightforward to design a deterministic TM that
generates these sequences. (See Problem 5.2 .)
Breadth-first search is used. Since a string w is accepted by a nondeterministic TM if
there is some choice input on which it is accepted, a deterministic TM M D that accepts the
input w accepted by M ND can be constructed by erasing the work tape, copying the input
sequence w to the work tape, placing the next choice input sequence in lexicographical or-
der on the enumeration tape (initially this is the sequence 0), and then simulating M ND on
the work tape while reading one choice input from the enumeration tape on each step. If
M D runs out of choice inputs before reaching the halt state, the above procedure is restarted
with the next choice input sequence. This method deterministically accepts the input string
w if and only if there is some choice input to M ND on which it is accepted.

Adding more than one tape to a nondeterministic Turing machine does not increase its
computing power. To see this, it suffices to simulate a multi-tape nondeterministic Turing
machine with a single-tape one, using a construction parallel to that of Theorem 5.2.1 ,and
then invoke the above result. Applying these observations to language acceptance yields the
following corollary.

COROLLARY 5.2.1 Any language accepted by a nondeterministic (multi-tape) Turing machine can
be accepted by a deterministic standard Turing machine.

We emphasize that this result does not mean that with identical resource bounds the de-
terministic and nondeterministic Turing machines compute the same set of functions.

5.2.3 Oracle Turing Machines
The oracle Turing machine (OTM) is a multi-tape TM or NDTM with a special oracle
tape and an associated oracle function h : B ∗ →B ∗ , which need not be computable. (See

Fig. 5.8 .) After writing a string z on its oracle tape, the OTM signals to the oracle to replace
z with the value h ( z ) of the oracle function. During a computation the OTM may consult