Alonzo Church
Encyclopedia
Alonzo Church was an American
mathematician
and logician who made major contributions to mathematical logic and the foundations of theoretical computer science
. He is best known for the lambda calculus
, Church–Turing thesis
, Frege–Church ontology, and the Church–Rosser theorem
.
where his father, Samuel Robbins Church, was the judge of the Municipal Court for the District of Columbia. The family later moved to Virginia after his father lost this position because of failing eyesight. With help from his uncle, also named Alonzo Church, he was able to attend the Ridgefield School for Boys in Ridgefield, Connecticut
. After graduating from Ridgefield in 1920, Church attended Princeton University
where he was an exceptional student, publishing his first paper, on Lorentz transformation
s, and graduating in 1924 with a degree in mathematics. He stayed at Princeton, earning a Ph.D.
in mathematics in three years under Oswald Veblen
.
He married Mary Julia Kuczinski in 1925 and the couple had three children, Alonzo Church, Jr. (1929), Mary Ann (1933) and Mildred (1938).
After receiving his Ph.D. he taught briefly as an instructor at the University of Chicago
and then received a two-year National Research Fellowship
. This allowed him to attend Harvard University
in 1927–1928 and then both University of Göttingen and University of Amsterdam the following year. He taught at Princeton, 1929–1967, and at the University of California, Los Angeles
, 1967–1990. In 1990, he received the Doctor Honoris Causa from the State University of New York at Buffalo in connection with an international symposium in his honor organized by John Corcoran
. He had previously received honorary doctorates from Case Western Reserve University
(1969) and Princeton University
(1985).
He died in 1995 and was buried in Princeton Cemetery
.
The lambda calculus emerged in his famous 1936 paper showing the unsolvability of the Entscheidungsproblem. This result preceded Alan Turing
's famous work on the halting problem
, which also demonstrated the existence of a problem unsolvable by mechanical means. Church and Turing then showed that the lambda calculus and the Turing machine
used in Turing's halting problem were equivalent in capabilities, and subsequently demonstrated a variety of alternative "mechanical processes for computation." This resulted in the Church–Turing thesis.
The lambda calculus influenced the design of the LISP programming language
and functional programming
languages in general. The Church encoding
is named in his honor.
, Peter B. Andrews, George A. Barnard
, William W. Boone, Martin Davis
, Alfred L. Foster, Leon Henkin
, John G. Kemeny
, Stephen C. Kleene
, Simon B. Kochen
, Maurice L'Abbé, Isaac Malitz
, Gary R. Mar
, Michael O. Rabin
, Nicholas Rescher
, Hartley Rogers, Jr., J. Barkley Rosser, Dana Scott
, Raymond Smullyan
, and Alan Turing
. A more complete list of Church's students is available via Mathematics Genealogy Project.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and logician who made major contributions to mathematical logic and the foundations of theoretical computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. He is best known for the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, Church–Turing thesis
Church–Turing thesis
In computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
, Frege–Church ontology, and the Church–Rosser theorem
Church–Rosser theorem
The Church–Rosser theorem states that if there are two distinct reductions starting from the same lambda calculus term, then there exists a term that is reachable from each reduct via a sequence of reductions...
.
Life
Alonzo Church was born on June 14, 1903 in Washington, D.C.Washington, D.C.
Washington, D.C., formally the District of Columbia and commonly referred to as Washington, "the District", or simply D.C., is the capital of the United States. On July 16, 1790, the United States Congress approved the creation of a permanent national capital as permitted by the U.S. Constitution....
where his father, Samuel Robbins Church, was the judge of the Municipal Court for the District of Columbia. The family later moved to Virginia after his father lost this position because of failing eyesight. With help from his uncle, also named Alonzo Church, he was able to attend the Ridgefield School for Boys in Ridgefield, Connecticut
Ridgefield, Connecticut
Ridgefield is a town in Fairfield County, Connecticut, United States. Situated in the foothills of the Berkshire Mountains, the 300-year-old community had a population of 24,638 at the 2010 census. The town center, which was formerly a borough, is defined by the U.S...
. After graduating from Ridgefield in 1920, Church attended Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
where he was an exceptional student, publishing his first paper, on Lorentz transformation
Lorentz transformation
In physics, the Lorentz transformation or Lorentz-Fitzgerald transformation describes how, according to the theory of special relativity, two observers' varying measurements of space and time can be converted into each other's frames of reference. It is named after the Dutch physicist Hendrik...
s, and graduating in 1924 with a degree in mathematics. He stayed at Princeton, earning a Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in mathematics in three years under Oswald Veblen
Oswald Veblen
Oswald Veblen was an American mathematician, geometer and topologist, whose work found application in atomic physics and the theory of relativity. He proved the Jordan curve theorem in 1905.-Life:...
.
He married Mary Julia Kuczinski in 1925 and the couple had three children, Alonzo Church, Jr. (1929), Mary Ann (1933) and Mildred (1938).
After receiving his Ph.D. he taught briefly as an instructor at the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
and then received a two-year National Research Fellowship
United States National Research Council
The National Research Council of the USA is the working arm of the United States National Academies, carrying out most of the studies done in their names.The National Academies include:* National Academy of Sciences...
. This allowed him to attend Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
in 1927–1928 and then both University of Göttingen and University of Amsterdam the following year. He taught at Princeton, 1929–1967, and at the University of California, Los Angeles
University of California, Los Angeles
The University of California, Los Angeles is a public research university located in the Westwood neighborhood of Los Angeles, California, USA. It was founded in 1919 as the "Southern Branch" of the University of California and is the second oldest of the ten campuses...
, 1967–1990. In 1990, he received the Doctor Honoris Causa from the State University of New York at Buffalo in connection with an international symposium in his honor organized by John Corcoran
John Corcoran (logician)
.John Corcoran is a logician, philosopher, mathematician, and historian of logic. He is best known for his philosophical work, helping us to understand such central concepts as the nature of inference, the relationship between logic and epistemology, and the place of proof theory and model theory...
. He had previously received honorary doctorates from Case Western Reserve University
Case Western Reserve University
Case Western Reserve University is a private research university located in Cleveland, Ohio, USA...
(1969) and Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
(1985).
He died in 1995 and was buried in Princeton Cemetery
Princeton Cemetery
Princeton Cemetery is located in Borough of Princeton, New Jersey. It is owned by the Nassau Presbyterian Church. John F. Hageman in his 1878 history of Princeton, New Jersey refers to the cemetery as: "The Westminster Abbey of the United States."...
.
Mathematical work
Church is best known for the following accomplishments:- His proof that the EntscheidungsproblemEntscheidungsproblemIn mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
, which asks for a decision procedure to determine the truth of arbitrary propositions in a mathematical theoryTheory (mathematical logic)In mathematical logic, a theory is a set of sentences in a formal language. Usually a deductive system is understood from context. An element \phi\in T of a theory T is then called an axiom of the theory, and any sentence that follows from the axioms is called a theorem of the theory. Every axiom...
, is undecidableUndecidable problemIn computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
for the theory of Peano arithmetic. This is known as Church's theorem. - His articulation of what has come to be known as Church–Turing thesisChurch–Turing thesisIn computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...
. - He was the founding editor of the Journal of Symbolic LogicJournal of Symbolic LogicThe Journal of Symbolic Logic is a peer-reviewed mathematics journal published quarterly by Association for Symbolic Logic.Founded in 1936, the journal publishes articles on mathematical logic....
, editing its reviews section until 1979. - His creation of the lambda calculusLambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
.
The lambda calculus emerged in his famous 1936 paper showing the unsolvability of the Entscheidungsproblem. This result preceded Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
's famous work on the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, which also demonstrated the existence of a problem unsolvable by mechanical means. Church and Turing then showed that the lambda calculus and the Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
used in Turing's halting problem were equivalent in capabilities, and subsequently demonstrated a variety of alternative "mechanical processes for computation." This resulted in the Church–Turing thesis.
The lambda calculus influenced the design of the LISP programming language
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
and functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
languages in general. The Church encoding
Church encoding
In mathematics, Church encoding is a means of embedding data and operators into the lambda calculus, the most familiar form being the Church numerals, a representation of the natural numbers using lambda notation...
is named in his honor.
Students
Many of Church's doctoral students have led distinguished careers, including C. Anthony AndersonC. Anthony Anderson
Curtis Anthony Anderson is a contemporary American philosopher, presently Professor of Philosophy at the University of California at Santa Barbara. He earned his Ph.D. in philosophy from University of California at Los Angeles in 1977, where he worked closely with the ground-breaking logician...
, Peter B. Andrews, George A. Barnard
George Alfred Barnard
George Alfred Barnard was a British statistician known particularly for his work on the foundations of statistics and on quality control.-Biography:...
, William W. Boone, Martin Davis
Martin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
, Alfred L. Foster, Leon Henkin
Leon Henkin
Leon Albert Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin's completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic.-The completeness proof:Henkin's result was not novel; it had...
, John G. Kemeny
John George Kemeny
John George Kemeny was a Hungarian American mathematician, computer scientist, and educator best known for co-developing the BASIC programming language in 1964 with Thomas E. Kurtz. Kemeny served as the 13th President of Dartmouth College from 1970 to 1981 and pioneered the use of computers in...
, Stephen C. Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
, Simon B. Kochen
Simon B. Kochen
Simon Bernhard Kochen is an American mathematician, working in the fields of model theory, number theory and quantum mechanics....
, Maurice L'Abbé, Isaac Malitz
Isaac Malitz
Isaac Richard Jay Malitz is a logician who introduced the subject of positive set theory in his 1976 Ph.D. Thesis at UCLA.- References :* – entry in the Mathematics Genealogy Project...
, Gary R. Mar
Gary R. Mar
Gary R. Mar is an American philosopher specializing in Logic, philosophy of mathematics, contemporary analytic philosophy, and philosophy of religion . He studied under the late logician Alonzo Church and currently teaches at Stony Brook University...
, Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
, Nicholas Rescher
Nicholas Rescher
Nicholas Rescher is an American philosopher at the University of Pittsburgh. In a productive research career extending over six decades, Rescher has established himself as a systematic philosopher of the old style and author of a system of pragmatic idealism which weaves together threads of...
, Hartley Rogers, Jr., J. Barkley Rosser, Dana Scott
Dana Scott
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...
, Raymond Smullyan
Raymond Smullyan
Raymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
, and Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
. A more complete list of Church's students is available via Mathematics Genealogy Project.
Books
- Alonzo Church, Introduction to Mathematical Logic (ISBN 978-0-691-02906-1)
- Alonzo Church, The Calculi of Lambda-Conversion (ISBN 978-0-691-08394-0)
- Alonzo Church, A Bibliography of Symbolic Logic, 1666–1935 (ISBN 978-0-8218-0084-3)
- C. Anthony Anderson and Michael Zelëny, editors, Logic, Meaning and Computation: Essays in Memory of Alonzo Church (ISBN 978-1-4020-0141-3)
Sources
, Alonzo Church: Life and Work. Introduction to the Collected Works of Alonzo Church, MIT Press, not yet published., In memoriam: Alonzo Church, The Bulletin of Symbolic Logic, vol. 1, no. 4 (Dec. 1995), pp. 486–488., Alonzo Church, 92, Theorist of the Limits of Mathematics (obituary), The New York Times, September 5, 1995, p. B6., 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., 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.
External links
- Princeton University Library, Manuscripts Division, The Alonzo Church Papers, 1924–1995: finding aid.
- A bibliography of Church's reviews for The Journal of Symbolic Logic, with a link to each