Nondeterministic Turing Machine
Also found in: Wikipedia.
Nondeterministic Turing Machine
(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
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
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)