Material Insights · Understanding the Material World

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
Mathematics and information · The science behind technology

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
  1. Church, working independently of Turing, had reached his own answer to the Entscheidungsproblem a few months earlier.
  2. Turing's universal machine could in principle solve any mathematical problem that could be presented to it in symbolic form.
  3. The Manchester Baby ran a program from memory for the first time on 21 June 1948.
The journey
  1. 1 Hilbert's questionIs mathematics decidable? Posed in 1928
  2. 2 ChurchPublishes his own answer in 1936, a few months before Turing
  3. 3 Universal machineTuring's paper, issues of November and December 1936
  4. 4 Stored programEDVAC report introduces the concept to industry, 1945
  5. 5 First runManchester Baby runs a program from memory, 1948
Go deeper pick a tab to open it in full