Turing machine

A Turing machine is a formal model of a procedure, not a particular piece of physical hardware. In a standard description, it has a tape divided into cells that hold symbols, a head that scans one cell at a time, a finite set of internal states, and rules that determine its actions. Based on the current state and scanned symbol, a rule specifies what symbol to write, which direction to move the head, and the next state. A computation begins with an input encoded on the tape and proceeds one step at a time; it may halt with a result or continue indefinitely.

The tape is treated as extendable without a fixed bound, an idealization that gives the model room to represent arbitrarily long calculations. Formal presentations differ in details such as whether the tape extends in one or both directions, but standard variants capture the same class of computable functions. The model abstracts the logic of a computation rather than its running time, energy use or physical memory requirements.

A Turing machine can be represented by a finite description of its states and rules. A universal Turing machine takes such a description, together with the simulated machine’s input, and carries out the computation that the described machine would perform. In this sense a single abstract machine can simulate any Turing machine.

Universality gives a precise mathematical account of general-purpose computation: instructions and data can both be encoded as symbols and processed. It does not mean that practical computers use a literal tape-and-head mechanism. Instead, the universal machine is a tool for reasoning about the range of computations that different machine designs can perform.

Computability theory asks whether any algorithm can solve a problem in all cases, rather than how quickly or economically it can do so. A central result is the undecidability of the halting problem: there is no Turing machine that, for every possible machine and input, correctly determines whether that computation will eventually stop. The proof uses self-reference to show that a proposed universal decision procedure would lead to a contradiction.

The Church–Turing thesis links this formal model to the informal idea of an effective, mechanical procedure: it proposes that anything computable by such a procedure can be computed by a Turing machine. The thesis is not a theorem proved from the machine’s formal rules, because the notion of an effective procedure is informal. It should also be distinguished from claims about the speed or efficiency of real computers.

Alan Turing introduced the machines in his paper “On Computable Numbers, with an Application to the Entscheidungsproblem,” published in 1937 in the Proceedings of the London Mathematical Society. He used them to formalize effective calculation while investigating whether a general procedure could decide mathematical questions posed in logic.

The model became a foundation of computability theory and theoretical computer science. Its lasting contribution is not a blueprint for a particular computer, but a framework for proving both that certain tasks can be carried out by algorithms and that other precisely stated tasks cannot be solved algorithmically in general.