Non-deterministic Turing machine

related topics
{math, number, function}
{system, computer, user}
{law, state, case}
{math, energy, light}

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal "state" and what number 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', change it to a 'B' and move left."

In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set.

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; rather, 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.

Contents

Definition

A nondeterministic Turing machine can be formally defined as a 6-tuple M=(Q, \Sigma, \iota, \sqcup, A, \delta), where

  • Q is a finite set of states
  • Σ is a finite set of symbols (the tape alphabet)
  • \iota \in Q is the initial state
  • \sqcup \in \Sigma is the blank symbol
  • A \subseteq Q is the set of accepting states
  • \delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times \{L,R\} \right) is a relation on states and symbols called the transition relation..

The difference with a standard (deterministic) Turing machine is that for those, the transition relation is a function (the transition function).

Full article ▸

related documents
Data integrity
Merge algorithm
NC (complexity)
C shell
Bucket sort
Removable singularity
Haar wavelet
Symbolic logic
Directed set
Axiom of extensionality
Hilbert's basis theorem
Addition of natural numbers
Snake lemma
Generating set of a group
Recursively enumerable language
Equality (mathematics)
Unique factorization domain
Bogosort
Finitely generated abelian group
Concatenation
Wreath product
Cauchy's integral theorem
Sharp-P-complete
Atlas (topology)
Boundary (topology)
Graph of a function
Vector calculus
Commutative diagram
Quadratic programming
BQP