Definition:Nondeterministic Turing Machine

From ProofWiki
Jump to navigation Jump to search



Definition

A Nondeterministic (or Non-deterministic) 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.



Formal Definition

A nondeterministic Turing machine is a 7-tuple $\paren {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 see

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




Source of Name

This entry was named for Alan Mathison Turing.


Sources