The Turing Machine
A Turing machine is an abstract device with an infinite tape and a finite rulebook that defines the mathematical limit of what is computable.
The parts
A Turing machine has an infinite tape divided into cells, a head that reads and writes one cell at a time, a finite set of internal states, and a transition rule. On each step it reads the symbol under the head, and based on that symbol and its current state it writes a symbol, moves the head left or right, and switches to a new state.
How it runs
The machine starts in a designated start state with the input written on the tape. It applies its transition rule repeatedly. If it reaches a halting state, whatever remains on the tape is the output. Some inputs may cause it to run forever, which is the crux of the halting problem.
Why so simple
The point of the model is not efficiency but generality. With only these primitive operations, a Turing machine can compute anything that any physical computer can compute. Adding more tapes, more heads, or nondeterminism does not extend what is computable, only how conveniently or how fast it is described.
Configurations
At any moment the machine's full situation is captured by its state, the tape contents, and the head position. This triple is a configuration. A computation is a sequence of configurations, each following from the last by one rule. Reasoning about computations means reasoning about these sequences.
- Tape: unbounded storage, one symbol per cell
- Head: reads, writes, moves one cell per step
- States: finite memory of "where you are" in the procedure
- Transition rule: the entire program
Universal machines
A single universal Turing machine can simulate any other Turing machine given a description of it on the tape. This is the theoretical ancestor of the stored-program computer: code and data live in the same memory. Every laptop is, up to finite memory, a universal machine.