nondeterministic Turing machines
(60 minutes to learn)
Summary
Nondeterministic Turing machines are a variant of Turing machines which can have multiple possible actions in a given state. They accept an input if there is any possible execution path which accepts it. They are no more powerful than ordinary Turing machines in terms of what they can compute, but are believed to be much more powerful in terms of what they can compute efficiently.
Context
This concept has the prerequisites:
Goals
- Define a nondeterministic Turing machine
- Show that a single-track Turing machine can simulate a multi-track Turing machine
- Show that a multi-track Turing machine (and therefore also a single-track one) can simulate a nondeterministic Turing machine
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
Other notes:
- Click on "Preview" to see the lecture videos.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 3.2, "Variants of Turing machines," pages 148-154
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 8.4, "Extensions to the basic Turing machine," pages 343-349
See also
-No Additional Notes-