must look at the effect of nondeterminism in more detail if we want to argue that
nondeterminism adds nothing to the power of a Turing machine. Again we resort
to simulation, showing that nondeterministic behavior can be handled
deterministically.
Definition 10.2
A nondeterministic Turing machine is an automaton as given by Definition
9.1, except that δ is now a function
δ : Q × Γ → 2 Q×Γ×{L, R} .
As always when nondeterminism is involved, the range of δ is a set of possible
transitions, any of which can be chosen by the machine.
Example 10.2
If a Turing machine has transitions specified by
δ (q 0 ,a) = {(q 1 ,b, R), (q 2 ,c, L)},
it is nondeterministic. The moves
and
are both possible.
Since it is not clear what role nondeterminism plays in computing functions,
nondeterministic automata are usually viewed as accepters. A nondeterministic
Turing machine is said to accept w if there is any possible sequence of moves
such that
nondeterminism adds nothing to the power of a Turing machine. Again we resort
to simulation, showing that nondeterministic behavior can be handled
deterministically.
Definition 10.2
A nondeterministic Turing machine is an automaton as given by Definition
9.1, except that δ is now a function
δ : Q × Γ → 2 Q×Γ×{L, R} .
As always when nondeterminism is involved, the range of δ is a set of possible
transitions, any of which can be chosen by the machine.
Example 10.2
If a Turing machine has transitions specified by
δ (q 0 ,a) = {(q 1 ,b, R), (q 2 ,c, L)},
it is nondeterministic. The moves
and
are both possible.
Since it is not clear what role nondeterminism plays in computing functions,
nondeterministic automata are usually viewed as accepters. A nondeterministic
Turing machine is said to accept w if there is any possible sequence of moves
such that