= Turing machine
{c}
{wiki}
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.<On Computable Numbers, with an Application to the Entscheidungsproblem by Alan Turing>[§§1–3]{ref} <Multitape Turing machines> change the storage organization and possible step counts while retaining the same computability power.
Back to article page
