(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 25 March 2019.
HTML page formatted Mon Mar 25 12:35:26 2019.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "nondeterministic Turing machine", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 25 March 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/nondetermTuringMach.html