Alonzo Church
Mathematician & Logician
About
Alonzo Church (1903–1995) was an American mathematician and logician who, working at Princeton, gave one of the two foundational definitions of computation. His lambda calculus captured the notion of an effectively calculable function through pure symbol substitution, and in 1936 he proved that the Entscheidungsproblem — Hilbert's dream of a general decision procedure for mathematics — has no solution. That same year, independently, Alan Turing reached the same boundary with his imaginary machines; their equivalence became the Church–Turing thesis, the bedrock claim about what computation is. Turing came to Princeton as Church's doctoral student. Church later held the Flint Professorship at UCLA (1967–1990).
Key Contributions
- Created the lambda calculus, a foundational model of computation still central to computer science
- Proved the undecidability of the Entscheidungsproblem (1936), independently of Turing
- Co-originated the Church–Turing thesis on the limits of effective computation
- Supervised Alan Turing's doctoral work at Princeton
- Founded the Journal of Symbolic Logic and shaped modern mathematical logic
Questions they sharpened View the streams
Papers & Publications
Connections
Alan Turing
InfluencedMathematician & Computer Science Pioneer
Turing came to Princeton in 1936 to write his doctorate under Church — the one man who had reached the same boundary first, and by a completely different road. Church's lambda calculus defined computation as pure substitution; Turing's machine defined it as a clerk with a tape. That the two turned out to describe exactly the same class of procedures became the Church–Turing thesis, the closest thing computer science has to a law of nature.
plato.stanford.edu · en.wikipedia.org · On Computable Numbers, with an Application to the Entscheidungsproblem (1936)
John McCarthy
InfluencedComputer Scientist & Father of AI
Lisp's lambda comes straight from Church, and McCarthy said so plainly: 'it seemed natural to use the λ-notation of Church (1941). I didn't understand the rest of his book, so I wasn't tempted to try to implement his more general mechanism for defining functions.' A logician's calculus became a working programming construct through a borrowing its borrower described as partial. Half the ancestry of AI's first language runs back to a 1936 proof about the limits of mathematics.
www-formal.stanford.edu · www-formal.stanford.edu
