Church, Alonzo

(b. 14 June 1903 in Washington, D.C.; d. 11 August 1995 in Hudson, Ohio), mathematician, logician, philosopher of mathematics, and computer scientist best known for three contributions to mathematical logic: Church’s thesis, Church’s theorem, and the lambda calculus.

Church was the son of Samuel Robbins Church, a judge, and Mildred Hannah Letterman Parker, a homemaker. Among his namesake ancestors were Alonzo Church (1793–1862), president of the University of Georgia from 1829 to 1859, and Alonzo Webster Church (b. 1829), a librarian and bibliographer. His brother, Randolph Warner Church (1907–1984), was the state librarian of Virginia from 1947 to 1972.

After graduating from Ridgefield High School, Connecticut, in 1920, Church entered Princeton University. During his sophomore year he won the prestigious Class of 1861 prize in mathematics. He became the protégé of Oswald Veblen, who urged him to pursue graduate study in mathematics. Among his other teachers were Luther Eisenhart, Henry Burchard Fine, Joseph H. M. Wedderburn, James W. Alexander II, and Einar Hille. On 25 August 1925 he married Mary Julia Kuczinski, a nurse. They had a son and two daughters.

Princeton awarded Church his A.B. in 1924 and his Ph.D. in 1927, both in mathematics. His doctoral dissertation, “Alternatives to Zermelo’s Assumption,” was published in 1927 in Transactions of the American Mathematical Society. From 1927 to 1929 he held a National Research Fellowship, spending the first year at Harvard University, the next half year in Göttingen, Germany, studying with David Hilbert, and the last half year in Amsterdam, Netherlands, studying with Luitzen Egbertus Jan Brouwer. Upon completing his fellowship, he returned to Princeton as assistant professor of mathematics. He was promoted to associate professor in 1939, full professor in 1947, and professor of mathematics and philosophy in 1961. He remained at Princeton until 1967. It was the perfect home for him. With the newly founded Institute for Advanced Study and the presence of such thinkers as Albert Einstein, Hermann Weyl, Eugene Paul Wigner, Oskar Morgenstern, Alan Turing, Kurt Gödel, Stephen C. Kleene, John Kemeny, Solomon Lefschetz, John von Neumann, Robert Oppenheimer, and Leon Henkin, Princeton in the 1930s and 1940s was the world’s most fertile environment for mathematical and scientific research.

Church began developing the lambda calculus in the late 1920s and published his earliest version in “A Set of Postulates for the Foundation of Logic,” Annals of Mathematics 33 (1932). After several more papers on this topic, he put the whole system into a book, The Calculi of Lambda-Conversion (1941). In the lambda calculus there are no logical constants and all mathematical objects are functions. A term is lambda-definable if and only if it is definable as a function in the lambda calculus. Lambda-definability was a prerequisite to the invention of digital computers, and the lambda calculus is a linchpin of computer science.

Church first proposed the thesis that bears his name at the meeting of the American Mathematical Society in April 1935. He first published it in “Abstract 205,” Bulletin of the American Mathematical Society (May 1935), and more fully in “An Unsolvable Problem in Elementary Number Theory,” American Journal of Mathematics 58 (1936). It argues that a mechanical or rule-governed algorithm for computing a function is possible just in case the function is recursive. As of 2000, it had not been proved, but a great deal of evidence had been presented to support it. Named “Church’s thesis” by Kleene in 1952, it is sometimes called the “Church-Turing thesis” because Turing, who in 1935 was Maxwell Herman Alexander Newman’s graduate student at Cambridge University, independently and simultaneously achieved the same result as Church. Newman assured the mathematical community that Turing had not stolen anything from Church, and Turing became Church’s graduate student at Princeton in 1936. Another expression of Church’s thesis is that a function is computable if and only if it is lambda-definable, that is, if and only if it is computable in a Turing machine.

Church’s theorem is not to be confused with Church’s thesis. Church published the theorem in “A Note on the Entscheidungsproblem,” Journal of Symbolic Logic 1 (1936). It is sometimes called the “Church-Turing undecidability theorem” because there is some overlap between Church’s result and what Turing wrote in “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society 42 (1936). Church and Turing were each studying decidability and undecidability in the wake of Godel’s two incompleteness proofs (1931), which show that for every consistent formal system adequate for arithmetic, there is at least one well-formed sentence in that system that cannot be proved within the system. Church’s theorem proves that first-order predicate logic is undecidable.

In 1936 Church cofounded the Association for Symbolic Logic; he was an editor of its major periodical, the Journal of Symbolic Logic, from 1936 to 1979. The first edition of his Introduction to Mathematical Logic, which became a standard text, appeared in 1944. In 1967 he became professor of philosophy at the University of California at Los Angeles (UCLA). In 1978 he was elected to the National Academy of Sciences. In 1984 his revised and expanded Bibliography of Symbolic Logic, 1666–1935 appeared, reprinted from the Journal of Symbolic Logic.

Church retired from UCLA in 1990. Two years later, in order to be near his son, Alonzo, Jr., he moved to Hudson, Ohio, where he died of natural causes. His funeral was in the Marquand Transept of the Princeton University Chapel, 14 August 1995, with burial in Princeton Cemetery.

Church was preeminent among twentieth-century logicians. Colleagues admired the painstaking care he took in every aspect of his life. His devotion to exactitude in teaching, editing, writing, and theorizing sometimes manifested itself as fastidiousness. He would, for example, use different colors of ink to express different ideas in his correspondence.

Information about Church’s life and work is available in the Princeton University archives and through the Princeton department of mathematics. Especially useful among these papers is the transcript of William Aspray’s 1984 interview with Church. The second edition of the Cambridge Dictionary of Philosophy (1999) includes John Corcoran’s clear assessment of Church’s place in the history of logic. Obituaries are in the New York Times (5 Sept. 1995); the History of Logic Newsletter 19 (1995): 1-2; Modern Logic 5 (1995): 408-412; and the Bulletin of Symbolic Logic 1 (1995): 486-488.

Eric v. d. Luft