Nondeterministic Turing Machine

Computing Dictionary

Nondeterministic Turing Machine definition

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
Explore Dictionary.com
Next Definition: nondeterrent
More from Thesaurus.com
Synonyms and Antonyms for nondeterministic turing machine
More from Reference.com
Search for articles containing nondeterministic turing machine
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature