A Turing machine is an abstract computational device introduced by Alan Turing in his 1936 paper to investigate what can be computed. It consists of a finite set of internal states, an infinite one-dimensional tape divided into squares, a read-write head that scans one square at a time, and a program of transition rules. At any given moment the machine’s behavior is completely determined by its current state and the symbol it is scanning, so the device operates deterministically.
Each transition rule specifies, for a given state and scanned symbol, what symbol to write, whether to move the head left or right, and which state to enter next. From this very small set of operations, repeated step by step, the machine can carry out arbitrarily complex calculations.
Turing originally called these devices automatic machines, or a-machines, to distinguish them from choice machines that require external decisions; Alonzo Church named them Turing machines in a 1937 review. Turing designed them specifically for the computation of real numbers and to formalize the intuitive notion of an effective procedure.
The Turing machine is now treated as a foundational model in computability theory and theoretical computer science. It gives a precise definition of which functions are computable and serves as the reference point against which the power of other models of computation is measured.