Work · Science & Human Sciences
On Computable Numbers, with an Application to the Entscheidungsproblem
Paper in the Proceedings of the London Mathematical Society: a machine that reads and writes symbols on a tape captures what a person calculating by a fixed rule can do; one “universal” machine can do the work of any other, and Hilbert’s decision problem has no mechanical solution – a result Alonzo Church reached at the same time by other means.
Introduction
Turing, a young fellow of King’s College, Cambridge, came to the problem through Max Newman’s lectures on the foundations of mathematics in 1935: Hilbert had asked whether there is a mechanical method for deciding of any formula of logic whether it is provable. The London Mathematical Society received the paper in May 1936, and it appeared in its Proceedings in 1936–37. Turing analyses what a person does when calculating by rule and reduces it to a machine with finitely many states that reads, writes and moves along an unbounded tape; “computable numbers” are the real numbers whose decimals such a machine can write out. He shows that a single universal machine can imitate any other if given its description, and that no machine can decide of every machine whether it will ever print a given symbol – from which the negative answer to Hilbert’s question follows. Alonzo Church had published the same answer shortly before, using his lambda calculus; in an appendix Turing proved the two notions of computability equivalent, and in the autumn of 1936 he went to Princeton, where he took his doctorate under Church in 1938.
Connections
Builds on
- On Formally Undecidable Propositions of Principia Mathematica and Related Systems I1931 · Kurt Gödel
Taken up in
- Computing Machinery and Intelligence1950 · Alan Turing
More works by Alan Turing
Sources: Wikidata
As of November 2026 · Improve this page · How Agora is made