Encyclopedia > Nondeterministic Turing machine

  Article Content

Non-deterministic Turing machine

Redirected from Nondeterministic Turing machine

An ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s', q', d), where s' is the symbol to be written by the head, q' is the subsequent state of the computer, and d is the direction (left or right) in which to step.

A NTM differs in that, rather than a single instruction triplet, the transition rule may specify a number of alternate instructions. At each step of the computation we can imagine that the computer "branches" into many copies, each of which executes one of the possible instructions. Whereas a DTM has a single "computation path" that it follows, a NTM has a "computation tree". If any branch of the tree halts with an "accept" condition, we say that the NTM accepts the input.

Intuitively it seems that the NTM is more powerful than the DTM, since it can execute many possible computations in parallel, requiring only that one of them succeeds. Any computation carried out by a NTM can be simulated by a DTM, although it may require significantly longer time. How much longer is not known in general - this is, in a nutshell, the definition of the "Is P = NP?" problem (see Complexity classes P and NP).



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Quadratic formula

... is now in a form in which we can conveniently complete the square[?]. To "complete the square" is to add a constant (i.e., in this case, a quantity that does not depend ...

 
 
 
This page was created in 22.7 ms