In theoretical computer science and computational theory, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike the standard, deterministic, Turing machine. NTMs are sometimes used in thought experiments to examine the abilities and limits of computers. One of the most important open problems in theoretical computer science is the P versus NP problem, which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer.
Background Alan Turing first developed the concept of Turing machine in 1936, imagining it as a simple computer that reads and writes symbols on an endless tape, one at a time, and by strictly following a predefined set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3."
Deterministic Turing machine In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. Such a machine 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 (it may be the same as the symbol currently in that position, or not even write at all, resulting in no practical change), the direction (left, right or neither) 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.
Description
In contrast to a deterministic Turing machine, in a nondeterministic Turing machine (NTM) the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to:
Write a Y, move right, and switch to state 5 or
Write an X, move left, and stay in state 3. Because there can be multiple actions that can follow from a given situation, there can be multiple possible sequences of steps that the NTM can take starting from a given input. If at least one of these possible sequences leads to an "accept" state, the NTM is said to accept the input. While a DTM has a single "computation path" that it follows, an NTM has a "computation tree".
Formal definition A nondeterministic Turing machine can be formally defined as a six-tuple M = ( Q , Σ , ι , ⊔ , A , δ ) {\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )} , where
Q {\displaystyle Q} is a finite set of states
Σ {\displaystyle \Sigma } is a finite set of symbols (the tape alphabet)
ι ∈ Q {\displaystyle \iota \in Q} is the initial state
⊔ ∈ Σ {\displaystyle \sqcup \in \Sigma } is the blank symbol
A ⊆ Q {\displaystyle A\subseteq Q} is the set of accepting (final) states
δ ⊆ ( Q ∖ A × Σ ) × ( Q × Σ × { L , S , R } ) {\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)} is a relation on states and symbols called the transition relation. L {\displaystyle L} is the movement to the left, S {\displaystyle S} is no movement, and R {\displaystyle R} is the movement to the right. The difference with a standard (deterministic) Turing machine is that, for deterministic Turing machines, the transition relation is a function rather than just a relation. Configurations and the yields relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the yields relation is no longer single-valued. (If the machine is deterministic, the possible computations are all prefixes of a single, possibly infinite, path.) The input for an NTM is provided in the same manner as for a deterministic Turing machine: the machine is started in the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise. An NTM accepts an input string if and only if at least one of the possible computational paths starting from that string puts the machine into an accepting state. When simulating the many branching paths of an NTM on a deterministic machine, we can stop the entire simulation as soon as any branch reaches an accepting state.
… excerpt ends here. Continue reading the full article.
