A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
More precisely, a Turing machine consists of:
- A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet.
- A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time.
- A state register that stores the state of the Turing machine, one of finitely many. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in.
- A finite table of instructions that, given the state the machine is currently in and the symbol it is reading on the tape, tells the machine to "erase / overwrite", "move the head" & finally "assume new state".