On Computable Numbers (Turing Machine)

Editorial record

Plain-language summary

Turing described a simple imagined device that reads and writes symbols on a tape according to a finite table of rules, and argued this captures anything a human clerk could compute by following steps. Using it he showed that a single 'universal' machine can simulate any other by reading its description, and that the halting problem has no general algorithmic solution. This gave a rigorous definition of 'algorithm' and 'computable', and the universal-machine idea underlies the concept of a programmable general-purpose computer.