Concept
Turing machine
An abstract machine that reads and writes symbols on an infinite tape according to a finite table of rules.
Updated Oct 21, 2026 · 1 min read · 5 connections
- Introduced
- 1936
- Proposed by
- Alan Turing
- Field
- Theory of computation
Definition
A Turing machine consists of a tape divided into cells, a head that reads and writes one cell at a time, and a finite set of states. At each step the current state and symbol determine what to write, which way to move, and the next state. Alan Turing described it to capture exactly what a person following fixed rules could compute.
Universality and limits
A universal Turing machine can simulate any other Turing machine given its description, which is the idea behind the stored-program computer. The same model shows that some problems, such as deciding whether an arbitrary program halts, have no algorithm.
The Church–Turing thesis holds that every effectively calculable function can be computed by a Turing machine, tying the model to formal logic.