with q f ∈ F. A nondeterministic machine may have moves available that lead to
a nonfinal state or to an infinite loop. But, as always with nondeterminism, these
alternatives are irrelevant; all we are interested in is the existence of some
sequence of moves leading to acceptance.
To show that a nondeterministic Turing machine is no more powerful than a
deterministic one, we need to provide a deterministic equivalent for the
nondeterminism. We have already alluded to one. Nondeterminism can be
viewed as a deterministic backtracking algorithm, and a deterministic machine
can simulate a nondeterministic one as long as it can handle the bookkeeping
involved in the backtracking. To see how this can be done simply, let us consider
an alternative view of nondeterminism, one which is useful in many arguments:
A nondeterministic machine can be seen as one that has the ability to replicate
itself whenever necessary. When more than one move is possible, the machine
produces as many replicas as needed and gives each replica the task of carrying
out one of the alternatives. This view of nondeterminism may seem particularly
nonmechanistic, since unlimited replication is certainly not within the power of
present-day computers. Nevertheless, a simulation is possible.
One way to visualize the simulation is to use a standard Turing machine,
keeping all possible instantaneous descriptions of the nondeterministic machine
on its tape, separated by some convention. Figure 10.14 shows a way in which
the two configurations aq 0 aa and bbq 1 a might appear. The symbols × are used to
delimit the area of interest, while + separates individual instantaneous
descriptions. The simulating machine looks at all active configurations and
updates them according to the program of the nondeterministic machine. New
configurations or expanding instantaneous descriptions will involve moving the
× markers. The details are certainly tedious, but not hard to visualize. Based on
this simulation, we conclude that for every nondeterministic Turing machine
there exists an equivalent deterministic standard machine.
Theorem 10.2
The class of deterministic Turing machines and the class of nondeterministic
Turing machines are equivalent.
Proof: Use the construction suggested above to show that any nondeterministic
Turing machine can be simulated by a deterministic one.
a nonfinal state or to an infinite loop. But, as always with nondeterminism, these
alternatives are irrelevant; all we are interested in is the existence of some
sequence of moves leading to acceptance.
To show that a nondeterministic Turing machine is no more powerful than a
deterministic one, we need to provide a deterministic equivalent for the
nondeterminism. We have already alluded to one. Nondeterminism can be
viewed as a deterministic backtracking algorithm, and a deterministic machine
can simulate a nondeterministic one as long as it can handle the bookkeeping
involved in the backtracking. To see how this can be done simply, let us consider
an alternative view of nondeterminism, one which is useful in many arguments:
A nondeterministic machine can be seen as one that has the ability to replicate
itself whenever necessary. When more than one move is possible, the machine
produces as many replicas as needed and gives each replica the task of carrying
out one of the alternatives. This view of nondeterminism may seem particularly
nonmechanistic, since unlimited replication is certainly not within the power of
present-day computers. Nevertheless, a simulation is possible.
One way to visualize the simulation is to use a standard Turing machine,
keeping all possible instantaneous descriptions of the nondeterministic machine
on its tape, separated by some convention. Figure 10.14 shows a way in which
the two configurations aq 0 aa and bbq 1 a might appear. The symbols × are used to
delimit the area of interest, while + separates individual instantaneous
descriptions. The simulating machine looks at all active configurations and
updates them according to the program of the nondeterministic machine. New
configurations or expanding instantaneous descriptions will involve moving the
× markers. The details are certainly tedious, but not hard to visualize. Based on
this simulation, we conclude that for every nondeterministic Turing machine
there exists an equivalent deterministic standard machine.
Theorem 10.2
The class of deterministic Turing machines and the class of nondeterministic
Turing machines are equivalent.
Proof: Use the construction suggested above to show that any nondeterministic
Turing machine can be simulated by a deterministic one.