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

q 1 q 2 q k q 1 q 2

q k

q q

(a) (b)

Figure 5.6 The construction used to reduce the fan-out of a nondeterministic state.

C = a ∈ Γ ∪{ β } , or it moves the head left (if possible) or right if C is L or R , respectively. If

δ ( q , c , a )= , there is no successor to the current state with choice input c and tape symbol a .

An NDTM M reads one character of its choice input string c

⊥

Σ ∗ on each step. An NDTM
M accepts string w if there is some choice string c such that the last state entered by M is h when
M is started in state s with w placed left-adjusted on its otherwise blank tape, and the tape head
at the leftmost tape cell. An NDTM M accepts the language L ( M )

∈

Γ ∗ consisting of those ⊆

strings w that it accepts. Thus, if w

∈ L ( M ) , there is no choice input for which M accepts w .

If an NDTM has more than two nondeterministic choices for a particular state and letter
under the tape head, we can design another NDTM that has at most two choices. As suggested
in Fig. 5.6 ,foreachstate q that has k possible next states q 1 , ... , q k for some input letter, we
can add k 2 intermediate states, each with two outgoing edges such that a) in each state the

tape head doesn't move and no change is made in the letter under the head, but b) each state
has the same k possible successor states. It follows that the new machine computes the same
function or accepts the same language as the original machine. Consequently, from this point
on we assume that there are either one or two next states from each state of an NDTM for
each tape symbol.
We now show that the range of computations that can be performed by deterministic and
nondeterministic Turing machines is the same. However, this does not mean that with the
identical resource bounds they compute the same set of functions.

−

THEOREM 5.2.2 Any language accepted by a nondeterministic standard TM can be accepted by a
standard deterministic one.

Proof The proof is by simulation. We simulate all possible computations of a nondeter-
ministic standard TM M ND on an input string w by a deterministic three-tape TM M D
and halt if we find a sequence of moves by M ND that leads to an accepting halt state. Later
this machine can be simulated by a one-tape TM. The three tapes of M D are an input
tape, a work tape, and enumeration tape .(SeeFig. 5.7 .) The input tape holds the in-
put and is never modified. The work tape is used to simulate M ND . The enumeration
tape contains choice sequences used by M D to decide which move to make when simu-