Turing machine

A Turing machine computes by repeatedly reading a symbol, changing state, writing a symbol, and moving its head left or right. Its tape is divided into cells, usually containing symbols from a finite alphabet, with a designated blank symbol; the finite control stores the current state. A transition function determines the next action for each permitted combination of state and scanned symbol.¹

Formal presentations commonly encode the machine as a tuple containing states, input and tape alphabets, a transition function, an initial state, and accepting or halting states. The model is intentionally austere: it has no built-in arithmetic, stack, random access, or high-level data structure. Those capabilities can be represented through suitable encodings and sequences of elementary operations.

The model defines computability rather than practical speed: a function is Turing-computable when some Turing machine eventually produces the required output for every input in its domain. This framework supports precise distinctions among decidable languages, recognizable languages, and problems for which no algorithm can always succeed.²

Turing's halting argument shows that no single machine can correctly determine, for every encoded machine and input, whether that computation will eventually stop. The proof uses diagonalization: a hypothetical universal halting tester can be turned into a machine that contradicts its own prediction. The result is a limit on computation itself, not merely on a particular programming language or hardware design.¹³

A universal Turing machine can simulate any other Turing machine when given an encoded description of that machine and its input. This separates program from data in a mathematically explicit way and anticipates the general-purpose architecture of modern stored-program computers.¹

The Church–Turing thesis proposes that the informal notion of an effectively calculable procedure coincides with what can be computed by a Turing machine. It is not a theorem derived from a formal definition of “effective procedure”; instead, it is supported by the convergence of several independent formalisms, including lambda calculus and recursive functions.² Turing machines are therefore used to compare computational models and establish computability-equivalence results, while complexity theory adds resource limits such as time and space.

The original 1936 formulation was motivated partly by the work of a human “computer” carrying out a calculation through discrete, locally observable steps, rather than by an attempt to describe an electronic machine.¹ Turing also described machines that can be configured by an encoded instruction sequence, an idea closely related to universality.

Many variants preserve the same computability power: tapes may be one-way or multi-track, heads may have several tapes, and transitions may permit different movement conventions. These changes can affect efficiency and the ease of proofs without changing which functions are computable.⁴ More specialized variants, including nondeterministic machines and oracle machines, are useful for complexity theory and mathematical logic, but they represent extensions of the basic model rather than replacements for its central role.

Computable function

A function for which a Turing machine produces the specified output after finitely many steps on every input in its domain.

Universal Turing machine

A Turing machine that simulates any machine described by an encoded specification and input.

Decidable language

A formal language whose membership can be determined by a Turing machine that halts on every input.

Halting problem

The undecidable problem of determining whether an arbitrary machine will eventually halt on a given input.

Church–Turing thesis

The claim that effectively calculable procedures are captured by the class of Turing-computable functions.