nondeterministic turing machine

1 definition found

nondeterministic turing machine - Free On-line Dictionary of Computing (26 May 2007) :

  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)