Definition:Nondeterministic Turing Machine

This article needs to be linked to other articles. In particular: all the technical terms: "halting state", "definite", "internal state", etc. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Definition

A nondeterministic Turing machine (NTM) is a variation of the classical Turing machine that relaxes the restriction that all the steps in the machine must be definite.

That is, given a single internal state and a single character being read on the tape the machine may have more than one possible response.

If any sequence of choices puts the machine into a halting state, then the machine stops after $n$ steps, where $n$ is the minimum number of steps needed to put the machine into a halting state.

This page needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code.

Formal Definition

A nondeterministic Turing machine is a $7$-tuple $\tuple {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ that satisfies the following:

• $Q$ is a finite set, the states of the machine.
• $\Sigma$ is a finite set, the input symbols.
• $\Gamma \supsetneq \Sigma$ is a finite superset of the input symbols, called the tape symbols.
  • For convenience, we also require that $\Gamma$ and $Q$ are disjoint.
• $\delta : Q \times \Gamma \to \powerset {Q \times \Gamma \times \set {L, R} }$ is a mapping, the transition function.
  • $L$ and $R$ are arbitrary constants called directions.
• $q_0 \in Q$ is a distinguished state called the start state.
• $B \in \Gamma$ is a distinguished tape symbol called the blank symbol. $B$ must not be an element of $\Sigma$.
• $F \subset Q$ be a designated subset of the states called accepting states.

An instantaneous description of a nondeterministic Turing machine is a finite sequence of elements of $\Gamma \cup Q$, subject to the following conditions:

• There is exactly one element of $Q$ in the sequence.
• The first entry in the sequence is not $B$.
• The last entry in the sequence is not in $Q$.
• If the last entry in the sequence is $B$, then the second-to-last is in $Q$.

By this definition, an instantaneous description can always be written as:

$X_m X_{m-1} \dotsm X_2 X_1 q Y Z_1 Z_2 \dotsm Z_{n-1} Z_n$

where $m$ or $n$ may be $0$; $X_i$, $Y$, and $Z_j$ are all elements of $\Gamma$; and $q$ is an element of $Q$.

Additionally, $X_m$ and $Z_n$ are not $B$ if they exist; that is, if $m$ and $n$ are not $0$, respectively.

A move reduces one instantaneous description into another by applying the transition function. There may be many possible moves from any given instantaneous description.

We write $A \vdash B$ if a machine with instantaneous description $A$ may have, after a single move, instantaneous description $B$.

Let $\paren{q', Y', d} \in \map \delta {q, Y}$.

Then there are seven cases to consider:

• If $d = L$ and $m > 0$, and either $n > 0$ or $Y' \neq B$ then:

$X_m \dotsm X_2 X_1 q Y Z_1 \dotsm Z_n \vdash X_m \dotsm X_2 q' X_1 Y' Z_1 \dotsm Z_n$

• If $d = L$ and $m > 0$, but $n = 0$ and $Y' = B$ then:

$X_m \dotsm X_2 X_1 q Y \vdash X_m \dotsm X_2 q' X_1$

• If $d = L$ but $m = 0$, and either $n > 0$ or $Y' \neq B$ then:

$q Y Z_1 \dotsm Z_n \vdash q' B Y' Z_1 \dotsm Z_n$

• If $d = R$ and $n > 0$, and either $m > 0$ or $Y' \neq B$ then:

$X_m \dotsm X_1 q Y Z_1 Z_2 \dotsm Z_n \vdash X_m \dotsm X_1 Y' q' Z_1 Z_2 \dotsm Z_n$

• If $d = R$ and $n > 0$, but $m = 0$ and $Y' = B$ then:

$q Y Z_1 Z_2 \dotsm Z_n \vdash q' Z_1 Z_2 \dotsm Z_n$

• If $d = R$ but $n = 0$, and either $m > 0$ or $Y' \neq B$ then:

$X_m \dotsm X_1 q Y \vdash X_m \dotsm X_1 Y' q' B$

• If $m = 0$, $n = 0$, and $Y' = B$ then regardless of $d$:

$q Y \vdash q' B$

Let $A \vdash^* B$ indicate that there exists a finite sequence $\sequence {A_i}_{0 \leq i \leq n}$ such that:

$A = A_0 \vdash A_1 \vdash A_2 \vdash \dotso \vdash A_n = B$

The language $\map L M$ accepted by the machine $M$ is the set of strings $w \in \Sigma^*$ for which, for some $\alpha, \beta \in \Gamma^*$ and $p \in F$:

$q_0 w \vdash^* \alpha p \beta$

As a special case, the null string is in the language if and only if the above holds for $w = B$.

Also known as

A nondeterministic Turing machine is also seen hyphenated as non-deterministic Turing machine.

Also see

Note that while a traditional Turing machine can be built or simulated rather easily, a NTM cannot actually be constructed.

• Nondeterministic Turing Machine is Equivalent to Deterministic Turing Machine

A particular theorem is missing. In particular: ... and as a consequence you can't actually construct a fully abstract TM without making some approximations that limit the applicability of the model You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding the theorem. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{TheoremWanted}} from the code.

• Definition:NP Complexity Class

Source of Name

This entry was named for Alan Mathison Turing.

Sources

• 2006: John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd ed.)