A precise definition of what can be computed. In 1936 Alonzo Church, with the lambda calculus, and Alan Turing, with an abstract machine, independently characterised mechanical procedures and proved that Hilbert's decision problem has no general solution.
We must know. We will know.
—— David Hilbert, closing words of his address "Naturerkennen und Logik" to the Society of German Scientists and Physicians, Königsberg, 8 September 1930 ("Wir müssen wissen. Wir werden wissen."), later inscribed on his grave in Göttingen; translated from the German
History
Computability concerns which problems can be settled by a finite set of mechanical rules in a finite number of steps. Leibniz dreamed of settling disputes by calculation, and "algorithm" descends from the name of the ninth-century Baghdad mathematician al-Khwarizmi. In 1928 David Hilbert and Wilhelm Ackermann posed the Entscheidungsproblem: find a general method that decides whether any formula of first-order logic is universally valid. On 7 September 1930, at a conference in Königsberg, Kurt Gödel first mentioned his incompleteness theorem; the next day Hilbert ended a lecture there with "We must know. We will know." Published in 1931, Gödel's theorem showed that any consistent formal system able to express arithmetic contains undecidable propositions. In 1936 Alonzo Church, using the lambda calculus, and Alan Turing, using an abstract machine, each defined "effectively calculable" and showed that the decision problem has no general solution. Turing's machine has a tape divided into squares, a head that reads and writes one square at a time, and finitely many internal states; he presented it as an abstraction of a person computing on paper "divided into squares like a child's arithmetic book". He also described a universal machine able to imitate any other, and in an appendix added in August 1936 proved the two definitions equivalent. Stephen Kleene later called the claim that they capture intuitive computability a thesis, now the Church–Turing thesis; Turing's undecidability result was later restated as the "halting problem".
Connections
Causes2
- Euclid's ElementsinspiresThe axiomatic ideal led, via Hilbert's programme, to the decision problem that Turing answered in the negative
- Alan TuringcontributedOn Computable Numbers (1936)
Consequences1
- The Electronic ComputerenablesThe universal machine is the theoretical prototype of the stored-program computer
Echoes1
- al-KhwārizmīechoesThe word “algorithm” comes from al-Khwarizmi's name
Sources
- A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (Proceedings of the London Mathematical Society, ser. 2, 42) (1936–37)
- Alonzo Church, An Unsolvable Problem of Elementary Number Theory (American Journal of Mathematics 58) (1936)
- Martin Davis, The Universal Computer: The Road from Leibniz to Turing (2000)
- Charles Petzold, The Annotated Turing (2008)
Open questionswell attested
- The name "halting problem" was coined later; Turing's original paper deals with deciding whether a machine is "circle-free".
- Emil Post independently proposed a model close to the Turing machine in 1936.
- How far Turing influenced the design of EDVAC is debated.
- Gödel's announcement and Hilbert's lecture came one after the other, and the two men did not confront each other directly at the time.
Why it matters
There is an irony at the heart of computability theory: to prove the limits of mechanical method, mathematicians had for the first time to define mechanical method exactly. Turing modelled his definition on a human computer working by rule, at a time when most scientific and engineering calculation was still done by people; once defined, computing came loose from any particular person or apparatus and became symbol manipulation that any suitable physical device might carry out. The universal machine, with instructions and data on the same tape, is often called the theoretical prototype of the stored-program computer. Von Neumann, whose EDVAC report of 1945 set out stored-program architecture, knew Turing's paper, but historians disagree about how far it shaped that design. The negative answer to the decision problem also meant that some questions can never be handed to a machine, and Hilbert's optimism met a limit drawn by logic itself.