nondeterministic Turing machines

(60 minutes to learn)


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.


This concept has the prerequisites:


  • 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)


Coursera: Automata
An introductory course on automata and the theory of computation.
Author: Jeffrey D. Ullman
Other notes:
  • Click on "Preview" to see the lecture videos.


See also

-No Additional Notes-