An Introduction to Formal Languages and Automata, 7th Edition

10.3 NONDETERMINISTIC TURING MACHINES

While Turing’s thesis makes it plausible that the specific tape structure is immaterial to the power of the Turing machine, the same cannot be said of nondeterminism. Since nondeterminism involves an element of choice and so has a nonmechanistic flavor, an appeal to Turing’s thesis is inappropriate. We 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

$$\delta :Q\times \Gamma \to 2^{Q\times \Gamma \times \left\{L,R\right\}}.$$

As always when ...