A Turing machine is an abstract model of computation consisting of an infinite tape, a read-write head, a finite set of states and a transition function that, given the current state and the symbol under the head, prescribes a symbol to write, a direction to move and a next state. Introduced by Alan Turing, it formalises the notion of an effective procedure and serves as the canonical definition of what is computable. The Church-Turing thesis holds that any function computable by any reasonable mechanism is computable by a Turing machine.
Overview
- Turing’s 1936 model captured the essence of mechanical calculation: a controller in one of finitely many states reads and writes symbols on a tape and moves left or right according to fixed rules.
- Despite its austerity, the model is universal: a single universal Turing machine can simulate any other given its description, prefiguring the stored-program computer.
- It underpins the theory of computability and complexity, framing questions of what can be computed and at what cost.
Key aspects
- Tape: an unbounded sequence of cells holding symbols from a finite alphabet.
- Head: reads and writes the current cell and moves one step per transition.
- Control: a Finite State Machine whose transition function drives behaviour.
- Universality: a universal machine simulates any machine from an encoded description.
- Decidability: the model exposes problems, such as the halting problem, that no algorithm can solve.
Mechanisms
- At each step the machine reads the symbol under the head, then writes a symbol, shifts, and changes state per the transition function.
- Computation halts when the machine enters a designated accepting or rejecting state, or runs forever.
- Variants such as multi-tape and nondeterministic machines are provably equivalent in computational power.
- The contrast with a finite-state model lies entirely in the unbounded, rewritable memory the tape provides.
Applications
- Foundational definition of computability and the reference for the Church-Turing thesis.
- Basis for computational complexity classes and reductions between problems.
- Conceptual grounding for theory underlying Artificial Intelligence and the limits of mechanised reasoning.
- Pedagogical model for understanding what general-purpose computers can and cannot do.