Nondeterministic Turing Machine

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
Mentioned in ?
References in periodicals archive ?
In computing science, however, nondeterminism has been an issue from the very beginning, if only in the form of nondeterministic Turing machines or nondeterministic finite state machines.
Algebraic approaches to nondeterminism: an overview

Encyclopedia browser ?
Full browser ?