Template:Turing machine formal overview

From LiteratePrograms
Jump to: navigation, search

[edit] Formal problem description and assumptions

We define a single-tape Turing machine as a 6-tuple M=(Q, \Gamma, q_0, \textvisiblespace, F, \delta), where

  • Q is a finite set of states;
  • Γ is the finite tape alphabet (the symbols that can occur on the tape);
  • q_0 \in Q is the initial state;
  • \textvisiblespace \in \Gamma is the blank symbol;
  • F \subseteq Q is the set of accepting (final) states;
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} is the transition function which determines the action performed at each step.

Initially the tape has the input string on it, followed by an infinite number of blank symbols (\textvisiblespace), and the head is at the left end of the tape. At each step we use the transition function to determine the next state, the symbol written on the tape just prior to moving, and the direction to move the head, left (L) or right (R). If we ever reach a final state, the machine halts.

This template is used by articles in Category:Turing machine simulators to give a formal overview of the particular Turing machine definition to be implemented.