Hyper Dictionary

English Dictionary Computer Dictionary Video Dictionary Thesaurus Dream Dictionary Medical Dictionary


Search Dictionary:  

Meaning of NONDETERMINISTIC TURING MACHINE

 
Computing Dictionary
 
 Definition: 

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

 

 

COPYRIGHT © 2000-2013 HYPERDICTIONARY.COM HOME | ABOUT HYPERDICTIONARY