Non-deterministic Turing machine
|
|
In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) 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 non-deterministic Turing machine (NTM) differs in that, rather than a single instruction triplet, the transition rule may specify a set of zero or more 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.
More formally, a k-tape non-deterministic Turing machine is a 6-tuple <math>M=(Q, \Sigma, \iota, \sqcup, A, \delta)<math>, where
- <math>Q<math> is a finite set of states
- <math>\Sigma<math> is a finite set of symbols (the tape alphabet)
- <math>\iota \in Q<math> is the initial state
- <math>\sqcup<math> is the blank symbol (<math>\sqcup \in \Sigma<math>)
- <math>A \subseteq Q<math> is the set of accepting states
- <math>\delta: Q \times \Sigma \rightarrow \mathcal{P} \left( Q \times \Sigma \times \{L,R\} \right)<math> is a partial function called the transition function, where L is left shift and R is right shift.
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).
It is a common misconception that quantum computers are NTMs. It is believed that the power of polynomial time quantum computers is incomparable to that of polynomial time NTMs. That is, for each of the two models, there is a problem that it can solve but the other model cannot. A likely example of problems solvable by NTMs but not by polynomial time quantum computers are NP-complete problems.
See also
External links
- C++ Simulator of a Nondeterministic Multitape Turing Machine (http://semillon.wpi.edu/~aofa/AofA/msg00020.html) (free software).zh:非确定型图灵机