Alonzo Church (1903 - 1995) was an American mathematician, logician, and philosopher whose work helped lay the theoretical foundations of computer science. [1] He is best known for creating the lambda calculus and for the Church-Turing thesis, which together shaped the modern understanding of computation and its limits. [2]
Early life and education
Alonzo Church was born in Washington, D.C., on 14 June 1903. He studied at Princeton University, receiving his undergraduate degree in 1924 and a doctorate in mathematics in 1927 under the supervision of Oswald Veblen. [3] He then held research fellowships in Europe and the United States, spending time at Harvard University, the University of Gottingen, and the University of Amsterdam before returning to Princeton, where he would spend most of his career.
The lambda calculus and computability
In the early 1930s Church developed the lambda calculus, a formal system for expressing computation through function abstraction and application. [2] Using it, he articulated what became known as Church's thesis: the proposal that the intuitive notion of an effectively calculable function coincides with a precise mathematical definition of computability. When combined with the independent work of his student Alan Turing on Turing machines, this became the Church-Turing thesis, a central principle of the theory of computation. [2]
In 1936 Church published a proof that no algorithm can decide whether an arbitrary statement of first-order logic is valid, resolving David Hilbert's Entscheidungsproblem in the negative. This result, now called Church's theorem, established fundamental limits on what can be decided by mechanical procedure. [2]
Career and the Journal of Symbolic Logic
Church taught at Princeton University from 1929 to 1967 and afterward at the University of California, Los Angeles, until his retirement in 1990. [3] In 1936 he helped found the Association for Symbolic Logic and its Journal of Symbolic Logic, which he edited for decades and whose extensive reviews section he shaped into an authoritative record of the field. [1] His 1956 textbook, Introduction to Mathematical Logic, became a standard reference.
Legacy
Church's ideas are foundational to theoretical computer science: the lambda calculus underlies functional programming languages and the formal study of computability. He supervised a remarkable group of doctoral students, including Alan Turing, Stephen Kleene, J. Barkley Rosser, Martin Davis, Michael Rabin, Dana Scott, and Leon Henkin. [4] Through this research and the students who extended it, Church exerted a lasting influence on logic, mathematics, and computing.
