What Are Turing Machines?

Turing machines are abstract mathematical models of computation that define, in precise formal terms, what it means for a function to be computable. Introduced by Alan Turing in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," a Turing machine consists of an infinite tape divided into cells, a read/write head that moves along the tape one cell at a time, a finite set of states, and a transition function that specifies what the machine writes, how the head moves, and which state it enters next, based solely on its current state and the symbol under the head. Simple as this description is, the model captures everything that any digital computer can compute.

Turing machines sit at the foundation of theoretical computer science. The formalism was developed independently of Alonzo Church's lambda calculus and Emil Post's production systems, yet all three models define the same class of computable functions, a convergence that gave rise to the Church-Turing thesis.

Formal Definition and Variants

A standard deterministic Turing machine is specified by a 7-tuple: the tape alphabet, the input alphabet, the blank symbol, the set of states, the initial state, the set of accepting states, and the transition function. The machine halts when it enters an accepting or rejecting state. Variants include multi-tape Turing machines, which use several independent tapes and heads; nondeterministic Turing machines, which can branch into multiple simultaneous computation paths; and probabilistic Turing machines, which make random choices at each step. Crucially, all these variants are computationally equivalent to the single-tape deterministic model in terms of the class of problems they can decide: any function computable by a multi-tape machine is also computable by a single-tape machine, though the number of steps may differ by a polynomial or greater factor. This equivalence is what gives the single-tape model its theoretical power as a universal yardstick. The Stanford Encyclopedia of Philosophy's entry on the Church-Turing Thesis provides a careful treatment of the relationship between the original Turing machine formalism and subsequent equivalent models of computation.

Computability and the Halting Problem

One of Turing's most significant results was the proof that certain well-posed mathematical problems are not computable by any Turing machine, no matter how large or how long it runs. The canonical example is the halting problem: given an arbitrary program and an input, determine whether the program will eventually terminate or loop forever. Turing proved in 1936 that no algorithm can solve this problem for all possible program-input pairs. The proof uses a diagonal argument in which a hypothetical halting-decider is used to construct a program that contradicts its own output, establishing a logical impossibility. The halting problem was the first decision problem proved undecidable, and it subsequently served as the reference point for proving the undecidability of many other problems in logic, linguistics, and program verification. Rice's theorem, which follows from the halting proof, states that no nontrivial property of a program's input-output behavior is decidable. The CS 251 computational theory notes from Wellesley College present the halting problem proof in a form accessible to students of computing while preserving the formal rigor of Turing's original argument.

The Church-Turing Thesis and Computational Complexity

The Church-Turing thesis asserts that any function intuitively regarded as computable by a human following a finite procedure can be computed by a Turing machine. This is not a theorem but a thesis, because "intuitively computable" is not formally defined. The thesis has remained unrefuted and serves as the foundation of computational complexity theory, which asks not merely whether a problem is computable but how efficiently: how many steps, and how much memory, as a function of input size. Complexity classes such as P (polynomial time) and NP (nondeterministic polynomial time) are defined in terms of resource bounds on Turing machines. The P versus NP question is the central open problem in the field, with direct implications for cryptography and algorithm design in digital computing systems. A formal treatment of complexity classes and their Turing-machine definitions appears in the ScienceDirect overview of Turing computability and complexity.

Applications

Turing machines have applications across a wide range of areas in computer science and engineering, including:

• Theoretical foundation for the design and analysis of all digital computers
• Formal definition of algorithm correctness and program verification
• Computational complexity analysis used in cryptography and algorithm design
• Proof of undecidability results that set limits on automated software testing
• Automata theory underlying compiler design and programming language specification
• Decision procedure research in artificial intelligence and formal verification tools