Alonzo Church was an
AmericanThe United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematicianA 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 scienceComputer 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 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...
,
Church–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...
, Frege–Church ontology, and the
Church–Rosser theoremThe 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., 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, ConnecticutRidgefield 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 UniversityPrinceton 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 transformationIn 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, 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 VeblenOswald 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 ChicagoThe 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 FellowshipThe 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 UniversityHarvard 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 AngelesThe 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 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 UniversityCase Western Reserve University is a private research university located in Cleveland, Ohio, USA...
(1969) and
Princeton UniversityPrinceton 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 CemeteryPrinceton 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 Entscheidungsproblem
In 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 theoryIn 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 undecidableIn 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 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...
.
- He was the founding editor of the Journal of Symbolic Logic
The 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 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...
.
The lambda calculus emerged in his famous 1936 paper showing the unsolvability of the Entscheidungsproblem. This result preceded
Alan TuringAlan 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 problemIn 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 machineA 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 languageLisp 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 programmingIn 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 encodingIn 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 AndersonCurtis 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. BarnardGeorge 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 DavisMartin 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 HenkinLeon 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. KemenyJohn 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. KleeneStephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
,
Simon B. KochenSimon Bernhard Kochen is an American mathematician, working in the fields of model theory, number theory and quantum mechanics....
, Maurice L'Abbé,
Isaac MalitzIsaac 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. MarGary 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. RabinMichael 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 RescherNicholas 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 ScottDana 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 SmullyanRaymond 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 TuringAlan 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.
External links