You are here: irt.org | FOLDOC | 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

(1995-04-27)

Nearby terms: nondeterministic « nondeterministic automaton « nondeterministic polynomial time « **Nondeterministic Turing Machine** » non-impact printer » non-interlaced » nonintrusive testing

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL