Sign in

Church's lambda calculus

1936Big moment

Alonzo Church uses lambda calculus to show some mathematical problems cannot be decided by any procedure. It later becomes the basis of functional programming.

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

  1. The Lambda Calculus Stanford Encyclopedia of Philosophy
  2. 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…

Learn more ranked by votes

Documentplato.stanford.edu
The Lambda Calculus (Stanford Encyclopedia of Philosophy)
Editor's pick
VideoSearch YouTube
lambda calculus explained
Search YouTube
VideoSearch YouTube
Alonzo Church Entscheidungsproblem
Search YouTube