No Mic Podcast Scribed By Facelesslingjutsu - Profile: Alonzo Church
Profiling Significant Figures or An Esteemed Guest
The only thing that might have annoyed some mathematicians was the presumption of assuming that maybe the axiom of choice could fail, and that we should look into contrary assumptions. - Alonzo Church
Alonzo Church (1903-1995) was a prominent American mathematician and logician whose work profoundly influenced the foundations of theoretical computer science. He is best known for developing the lambda calculus in the 1930s, a formal system for expressing computation based on function abstraction and application. This groundbreaking work provided a universal model of computation and laid the groundwork for functional programming languages.
Alonzo Church was born on June 14, 1903, in Washington, D.C., to Samuel Robbins Church, a judge, and Mildred Hannah Letterman Parker. His family had a notable academic lineage, with his great-grandfather, also named Alonzo Church, serving as a mathematics professor and later president of the University of Georgia.
Early in his childhood, a significant incident occurred when an air gun accident left him blind in one eye. Despite this, he excelled academically. With the help of an uncle, he attended the private Ridgefield School for Boys in Connecticut, graduating in 1920. That same year, he began his university education at Princeton, where he quickly demonstrated exceptional talent in mathematics. He earned his Bachelor of Arts degree in mathematics in 1924, followed by his Ph.D. in 1927. His doctoral work, supervised by Oswald Veblen, focused on foundational issues in mathematics, with his dissertation titled "Alternatives to Zermelo's Assumption."
After completing his doctorate, Church embarked on a period of intense study and research. He spent a year (1927-1928) as a National Research Fellow at Harvard University, followed by a year abroad (1928-1929) on an International Research Fellowship, studying at the prestigious University of Göttingen in Germany and the University of Amsterdam in the Netherlands, where he worked with renowned mathematician L.E.J. Brouwer. This foundational period of his life, marked by rigorous academic training and exposure to leading minds in logic and mathematics, set the stage for his groundbreaking contributions to theoretical computer science and mathematical logic in the decades that followed.
In 1929, Alonzo Church returned to Princeton University, joining the faculty as an Assistant Professor of Mathematics. This marked the beginning of a remarkable tenure that would span nearly four decades, transforming Princeton into a global hub for symbolic logic. He was promoted to Associate Professor in 1939 and full Professor in 1947, eventually becoming Professor of Mathematics and Philosophy.
The Lambda Calculus (Early 1930s): Church's most iconic creation was the lambda calculus. This formal system, based on function abstraction and application, provided a new way to express computation. It's an elegant and minimalist system, yet it proved to be remarkably powerful, capable of representing any computable function. The lambda calculus became a foundational concept for functional programming languages, influencing the design of languages like Lisp and Haskell, and remains a vital tool in programming language theory and type systems. His key work, "The Calculi of Lambda-Conversion," was published in 1941.
Church co-founded the Association for Symbolic Logic (ASL) in 1935 and served as its president from 1944 to 1947, shaping the organization’s early direction alongside his editorial work for The Journal of Symbolic Logic (1936–1979). His leadership in the ASL formalized logic as a discipline, fostering international collaboration and establishing standards for research. Including this role highlights his institutional contributions, complementing his editorial efforts and showing his broader impact on the logic community.
Church's Theorem and the Undecidability of First-Order Logic (1936): Expanding on the work of Kurt Gödel, Church proved a fundamental limitation of formal systems: there is no general algorithmic method to determine the truth or falsity of all mathematical statements in first-order logic. This result, known as Church's Theorem, demonstrated the inherent undecidability of certain computational problems, highlighting the boundaries of what can be algorithmically solved. It directly addressed David Hilbert's "Entscheidungsproblem" (decision problem), proving its unsolvability.
The Church-Turing Thesis (1936): In a pivotal intellectual convergence, Church and his doctoral student, Alan Turing, independently arrived at equivalent formalizations of the concept of "effective calculability." The Church-Turing thesis, named after both, states that any effectively calculable function can be computed by a Turing machine (Turing's model of computation) or, equivalently, by the lambda calculus (Church's model). This thesis is not a mathematical theorem to be proven but a widely accepted foundational principle of theoretical computer science, defining the very limits of what can be computed by mechanical or algorithmic processes.
Founding and Guiding The Journal of Symbolic Logic (1936-1979): Recognizing the burgeoning field of symbolic logic, Church was instrumental in establishing The Journal of Symbolic Logic in 1936. This publication became the premier venue for research in the field. Church served as an editor for its initial 44 volumes and, remarkably, as the editor of its influential reviews section for 43 years. His rigorous standards and meticulous guidance were crucial in shaping the discipline and fostering its growth, earning it respect among mathematicians and philosophers alike.
Alonzo Church mentored several influential logicians and computer scientists, including J. Barkley Rosser, Stephen Kleene, Martin Davis, and Leon Henkin, who advanced logic and computability theory under his guidance at Princeton (1930s–1960s). For example, Kleene’s work on recursive functions (1936–1940) and Rosser’s contributions to the Church–Kleene ordinal (1938) built directly on Church’s lambda calculus and computability framework. Highlighting his mentorship role underscores Church’s impact on shaping the next generation of scholars, establishing Princeton as a hub for logic, and fostering foundational developments in theoretical computer science, beyond his direct collaboration with Alan Turing.
Moreover, Church made significant philosophical contributions in intensional logic, beginning with "A Formulation of the Logic of Sense and Denotation" (1951). Building on Frege's work, his formal framework for analyzing meaning in natural language deeply influenced the philosophy of language and modal logic. This work, spanning from the 1950s well into his later years, highlights his significant interdisciplinary influence, reaching fields like linguistics and cognitive science, particularly in natural language processing and formal models of meaning. His computability results also informed early artificial intelligence research, demonstrating his wide-ranging impact.
"Introduction to Mathematical Logic" (1956): Church's textbook, "Introduction to Mathematical Logic," published in 1956, became a seminal work in the field. It served as a standard reference for generations of students and researchers, providing a comprehensive and rigorous exposition of formal logic. Even decades after its initial publication, it remains a valuable resource for understanding the foundations of logic.
Church's influence extended far beyond mathematics and directly impacted computer science beyond functional programming. The lambda calculus proved foundational for type theory, formal verification, and programming language semantics, with applications in compiler design and automated theorem proving. His lesser-known work, such as "Application of Recursive Arithmetic to the Problem of Circuit Synthesis" (1960), further demonstrated his versatility in connecting logical frameworks to practical computing challenges.
In 1967, after a distinguished career at Princeton, Church retired from the university. However, his intellectual curiosity and dedication to scholarship remained undiminished. He accepted a position as Kent Professor of Philosophy and Professor of Mathematics at the University of California, Los Angeles (UCLA). He continued his active research, teaching, and editorial work at UCLA until his second retirement in 1990.
At UCLA (1967–1990), Church continued research on intensional logic, publishing papers like “A Revised Formulation of the Logic of Sense and Denotation” (1993), and taught courses that influenced philosophy and mathematics students. His work in the 1970s–1990s bridged logic and philosophy, contributing to semantics and modal logic. Detailing this period would highlight his sustained productivity and influence late in his career, showing how he shaped UCLA’s academic environment in addition to his Princeton legacy.
Throughout his life, Church received numerous accolades, including election to the National Academy of Sciences in 1978 and the British Academy in 1980, as well as several honorary degrees. He passed away on August 11, 1995, at the age of 92, having lived to see the profound impact of the computer revolution that his foundational theoretical work helped to ignite. His legacy is one of intellectual precision, groundbreaking innovation, and a profound impact on the fields that bridge mathematics, logic, and computer science.
“Never had any mathematical conversations with anybody, because there was nobody else in my field.” - Alonzo Church
Awards:
Honorary Doctor of Science degrees:
Case Western Reserve University (1969)
Princeton University (1985)
University at Buffalo, The State University of New York (1990) - in connection with an international symposium held in his honor.
Memberships in prestigious academies:
Corresponding Fellow of the British Academy (FBA) (1966)
American Academy of Arts and Sciences (1967)
National Academy of Sciences (1978)
Complete works:
1924
Uniqueness of the Lorentz Transformation
1927
Alternatives to Zermelo’s Assumption
1932
A Set of Postulates for the Foundation of Logic
1933
A Set of Postulates for the Foundation of Logic (Part II)
1935
An Unsolvable Problem in Elementary Number Theory (Abstract)
1936
An Unsolvable Problem in Elementary Number Theory
A Note on the Entscheidungsproblem
1937
Correction to ‘A Note on the Entscheidungsproblem’
1938
The Constructive Second Number Class
1939
The Present Situation in the Foundations of Mathematics
1940
On the Concept of a Random Sequence
A Formulation of the Simple Theory of Types
1941
The Calculi of Lambda-Conversion
1943
Review of Quine’s Notes on Existence and Necessity
1944
Introduction to Mathematical Logic, Part I
1956
Introduction to Mathematical Logic, Volume I
1958
Ontological Commitment
1962
Logic, Arithmetic, and Automata
1963
Review of Quine’s From a Logical Point of View
1965
Axioms for Number-Theoretic Functions
1967
The Logic of Sense and Denotation (Revised)
1970
A Theory of the Meaning of Names
1971
Set Theory with a Universal Set
1973
Outline of a Revised Formulation of the Logic of Sense and Denotation (Part I)
1974
Outline of a Revised Formulation of the Logic of Sense and Denotation (Part II)
1976
Comparison of Russell’s Resolution of the Semantical Antinomies with That of Tarski
1982
Referee’s Report on Tarski’s Intuitionistic Logic and Logical Grammar
1983
Some Remarks on Modal Logic
1984
Intensional Semantics
1988
A Theory of Intensional Semantics for Natural Language
1995
A Note on Intensional Semantics
Unpublished Works (Included in The Collected Works of Alonzo Church, 2019, with Estimated Years)
A Bibliography of Symbolic Logic (1936)
Logic and Analysis for Natural Language (1972)
A Basic Logic (1974)
A Theory of Incompletely Defined Predicates (1975)
Some Remarks Concerning the General Theory of Relations (1980)
References
Enderton, Herbert B., Alonzo Church: Life and Work. Introduction to The Collected Works of Alonzo Church, MIT Press, 2019.
Enderton, Herbert B., In memoriam: Alonzo Church, The Bulletin of Symbolic Logic, vol. 1, no. 4 (Dec. 1995), pp. 486–488.
Wade, Nicholas, Alonzo Church, 92, Theorist of the Limits of Mathematics (obituary), The New York Times, September 5, 1995, p. B6.
Hodges, Wilfred, Obituary: Alonzo Church, The Independent (London), September 14, 1995.
Alonzo Church interviewed by William Aspray on 17 May 1984. The Princeton Mathematics Community in the 1930s: An Oral-History Project, transcript number 5.
Rota, Gian-Carlo, Fine Hall in its golden age: Remembrances of Princeton in the early fifties. In A Century of Mathematics in America, Part II, edited by Peter Duren, AMS History of Mathematics, vol 2, American Mathematical Society, 1989, pp. 223–226. Also available here.
Church, A. (1950). "On Carnap's Analysis of Statements of Assertion and Belief". The Journal of Symbolic Logic. 10 (5): 97–99. doi:10.2307/3326684. JSTOR 3326684.
Anderson, C. Anthony (1998). "Alonzo Church's contributions to philosophy and Intensional Logic". The Bulletin of Symbolic Logic. 4 (2): 129–171. CiteSeerX 10.1.1.26.7389. doi:10.2307/421020. JSTOR 421020. S2CID 18305417.