Try Our Apps
Dictionary.com

follow Dictionary.com

What is Ghosting?

nondeterministic turing machine

nondeterministic turing machine in Technology

complexity
A normal (deterministic) Turing Machine that has a "guessing head" - a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing Machine then runs and returns "yes" or "no" to indicate whether the solution is correct.
A nondeterministic Turing Machine can solve nondeterministic polynomial time computational decision problems in a number of steps that is a polynomial function of the size of the input
(1995-04-27)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source

Word of the Day

Word Value for nondeterministic

0
26
Scrabble Words With Friends

Nearby words for nondeterministic turing machine