Non-deterministic Turing machine
From Free net encyclopedia
Contents |
Description
In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left or right) in which the head should move, and the subsequent state of the finite control. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5.
A non-deterministic Turing machine (NTM) differs in that the state and tape symbol no longer uniquely specify these things - many different actions may apply for the same combination of state and symbol. For example, an X on the tape in state 3 might now allow the NTM to write a Y, move right, and switch to state 5 or to write an X, move left, and stay in state 3. In this sense, its finite control is akin to a non-deterministic finite automaton.
How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks the transition which eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. 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 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 \backslash A \times \Sigma \rightarrow \left( Q \times \Sigma \times \{L,R\} \right)</math> is a multivalued function over states and symbols called the transition function, where L is left shift and R is right shift. In conventional Turing machines, the transition function is not multi-valued.
Variations on this definition may replace the initial state with a set of initial states, and may include a set of rejecting states.
Intuitively it might seem that NTMs are more powerful than DTMs, since they can execute many possible computations at once, requiring only that any one of them succeeds. But any language recognized by a NTM can also be recognized by a DTM: the DTM can simulate each transition of the NTM, making multiple copies of the simulated state when multiple transitions are possible, and simulating them all in parallel, not unlike processes in a multitasking operating system.
It should be apparent that this simulation 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).
Comparison to Other Models of Computation
A NTM has the property of bounded nondeterminism, i.e., if a NTM always halts on a given input tape T<tt> then it halts in a bounded number of states (where a state is the total state of the machine including its tapes). This is in contrast to some models of concurrent computation such as the Actor model that have the property of unbounded nondeterminism. (See Unbounded nondeterminism.)
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 the one can solve but the other cannot. A likely example of problems solvable by NTMs but not by polynomial time quantum computers are NP-complete problems.
See also
References
- Papadimitriou, Christos. Computational Complexity. Addison-Wesley, 1995.
External links
- C++ Simulator of a Nondeterministic Multitape Turing Machine (free software).de:Nichtdeterministische Turingmaschine
ko:비결정론적 튜링 기계 ru:Недетерминированная машина Тьюринга tr:Belirlenimsiz Turing makinesi zh:非确定型图灵机