NIST

nondeterministic Turing machine

(definition)

Definition: A Turing machine which has more than one next state for some combinations of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance.

See also alternating Turing machine, oracle Turing machine, probabilistic Turing machine, universal Turing machine.

Note: A nondeterministic Turing machine is a probabilistic Turing machine ignoring the probabilities.

From Algorithms and Theory of Computation Handbook, page 24-9, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Implementation

Alex Vinokur's Turing machine simulator (C++).
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 21 November 2005.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "nondeterministic Turing machine", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 21 November 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/nondetermTuringMach.html