Turing machine

An abstract computing device consisting of an infinite tape divided into cells, a head that reads and writes one cell at a time and can move left or right, and a finite table of rules governing what the head does next based on the current state and the symbol it reads. Alan Turing introduced it in 1936 not as a machine to be built but as a precise definition of what it means for a function to be computable at all — a state machine with unbounded memory, and still the reference model against which every real computer’s theoretical power is measured.