# 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-