In theoretical computer science, a non-deterministic Turing machine (NTM) is a Turing machine whose control mechanism works like a non-deterministic finite automaton.

Description

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.

An 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.

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.

Definition

More formally, a non-deterministic Turing machine is a 6-tuple $M=(Q,\; \backslash Sigma,\; \backslash iota,\; \backslash sqcup,\; A,\; \backslash delta)$, where

• $Q$ is a finite set of states
• $\backslash Sigma$ is a finite set of symbols (the tape alphabet)
• $\backslash iota\; \backslash in\; Q$ is the initial state
• $\backslash sqcup$ is the blank symbol ($\backslash sqcup\; \backslash in\; \backslash Sigma$)
• $A\; \backslash subseteq\; Q$ is the set of accepting states
• $\backslash delta:\; Q\; \backslash backslash\; A\; \backslash times\; \backslash Sigma\; \backslash rightarrow\; \backslash left(\; Q\; \backslash times\; \backslash Sigma\; \backslash times\; \backslash \{L,R\backslash \}\; \backslash right)$ 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

There are a considerable number of variations on this definition. The initial state may be replaced by a set of initial states, for example. (This is equivalent because it is trivial to simulate multiple start states by adding a single start state which nondeterministically chooses which of the multiple start states to continue with.)

The variation may also include a set of rejecting states, in which case the NTM is said to reject if all computation paths lead to rejecting states.

Equivalence with DTMs

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 then it halts in a bounded number of configurations. (Note: this claim is disputed. See Non-deterministic Turing machine.) 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