Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  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 


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)


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017