Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tupleHere is a nonempty finite set of control states, a finite tape alphabet with a designated blank symbol , the input alphabet, the initial control state, and distinct halting control states. The transition function is total on the displayed domain. The Turing machine instruction means to write over the scanned , enter control state , and move the head one cell in direction .
A Turing machine configuration is , where , is the head position, and is the tape-content function, equal to outside a finite set. Its next-configuration relation isif , with for and for , andThere is no successor to either halting Turing machine configuration.
For input , the initial Turing machine configuration is , where for and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language isThe relation permits any finite number of transitions. An input outside may reach the rejecting control state or run forever; recognition does not require halting on every input.
Turing machine Created 2026-09-24 Updated 2026-11-05
A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.
In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.
The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.