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