The story
In 1936 the American logician Alonzo Church, working at Princeton University, published a paper called An Unsolvable Problem of Elementary Number Theory. Using a notation he had developed in the early 1930s, called the lambda calculus, he showed that there is no general procedure for deciding whether two expressions in this system are equivalent. He then used this to show that the Entscheidungsproblem, the 'decision problem' posed by David Hilbert and Wilhelm Ackermann in 1928, has no solution: no mechanical method can decide whether any statement of first-order logic is provable.
The result came out of the crisis in the foundations of mathematics. Hilbert had hoped that mathematicians could find a method that, given any mathematical statement, would settle it mechanically. In 1931 Kurt Gödel showed that arithmetic contains true statements that cannot be proved, which damaged the hope for completeness but left open whether a decision method could exist. Church's lambda calculus was a precise way of defining what a function and a computation are, using only abstraction and substitution of variables. Once 'effectively calculable' was defined, he could prove that some problems fall outside it.
Within months the British mathematician Alan Turing reached the same conclusion by a different route, with his imaginary machines, and then came to Princeton to study under Church, earning his PhD in 1938. The two definitions of computability, along with Gödel's recursive functions, turned out to be equivalent, which led to the Church-Turing thesis: anything that can be effectively computed can be computed by a Turing machine. Lambda calculus later became the foundation of functional programming. John McCarthy's Lisp (1958) drew on it, and so did languages such as Haskell and ML, and the anonymous 'lambda' functions found in Python, JavaScript and many other languages.
Why it mattered
- The Church-Turing thesis gave a precise definition of what any computer can and cannot calculate.
- Functional programming languages such as Lisp, ML and Haskell took the lambda calculus as their theoretical basis.
- The proof that logic has no general decision procedure ended Hilbert's hope of mechanizing all mathematics.
- Computability theory became a core part of computer science, shaping the study of algorithms and complexity.
Sources
- The Lambda Calculus Stanford Encyclopedia of Philosophy
- Supplement to Alonzo Church Stanford Encyclopedia of Philosophy
Drafted by AI (Claude) from the sources above and checked against them by AI; no historian has reviewed this page. Spot a mistake? Suggest a correction. How pages are made
Community notes
Loading notes…