Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap

Nondeterministic Turing Machine

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


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

©2018 Martin Webb