Computability and the universal machine
One machine following stored instructions can compute anything that is computable.
Mathematics and information · Theory of computation · No. 124
- Electrical and chemical age
- Science
Turing described in 1936 a machine that can imitate any other, and proved that some questions no machine can answer.
Chart: Illustration: Computability and the universal machine
Where it comes from
Chart: Map of where it comes from
Hilbert posed three questions about mathematics in 1928, the last being whether it is decidable. Church and, independently, Turing answered it in 1936, Turing a few months later with a machine that formalised computing.
Three things to know
- Church, working independently of Turing, had reached his own answer to the Entscheidungsproblem a few months earlier.
- Turing's universal machine could in principle solve any mathematical problem that could be presented to it in symbolic form.
- The Manchester Baby ran a program from memory for the first time on 21 June 1948.
The journey
- 1 Hilbert's questionIs mathematics decidable? Posed in 1928
- 2 ChurchPublishes his own answer in 1936, a few months before Turing
- 3 Universal machineTuring's paper, issues of November and December 1936
- 4 Stored programEDVAC report introduces the concept to industry, 1945
- 5 First runManchester Baby runs a program from memory, 1948