Alonzo Church (June 14, 1903 – August 11, 1995) 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 and/or research is the field of mathematics. Mathematicians are concerned with particular problems related to logic, space, transformations, numbers and more general ideas which encompass these concepts...
and
logician who made major contributions to mathematical logic and the foundations of theoretical
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
. 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. It was introduced by Alonzo Church in 1932 as part of an investigation into the foundations of mathematics...
,
Church–Turing thesisIn computability theory the Church–Turing thesis is a combined hypothesis about the nature of effectively calculable functions by recursion , by mechanical device equivalent to a Turing machine or by use of Church's λ-calculus...
, 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...
.
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, founded on July 16, 1790...
where his father, Samuel Robbins Church, was the Justice of the Municipal Court for the District of Columbia.
Alonzo Church (June 14, 1903 – August 11, 1995) 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 and/or research is the field of mathematics. Mathematicians are concerned with particular problems related to logic, space, transformations, numbers and more general ideas which encompass these concepts...
and
logician who made major contributions to mathematical logic and the foundations of theoretical
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
. 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. It was introduced by Alonzo Church in 1932 as part of an investigation into the foundations of mathematics...
,
Church–Turing thesisIn computability theory the Church–Turing thesis is a combined hypothesis about the nature of effectively calculable functions by recursion , by mechanical device equivalent to a Turing machine or by use of Church's λ-calculus...
, 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, founded on July 16, 1790...
where his father, Samuel Robbins Church, was the Justice 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 23,643 at the 2000 census, spread across . In the 2000 census, the town center, which was formerly a borough, was defined by the...
. After graduating from Ridgefield in 1920, Church attended
Princeton UniversityPrinceton University a private university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League and is considered one of the Colonial Colleges....
where he was an exceptional student, publishing his first paper, on
Lorentz transformationIn physics, the Lorentz 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 frame of reference. It reflects the surprising fact that observers moving at different velocities report...
, and graduating in 1924 with a degree in mathematics. He stayed on at Princeton, earning a
Ph.D.Doctor of Philosophy, abbreviated PhD , for the Latin , meaning "teacher of philosophy", or alternatively, DPhil, for the equivalent , is an advanced 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, coeducational research university in Chicago, Illinois, USA. It was founded by oil magnate and benefactor John D...
and then received a two-year
National Research FellowshipThe National Research Council of the USA is the working arm of the United States National Academy of Sciences and the United States National Academy of Engineering, carrying out most of the studies done in their names.-History:...
. This allowed him to attend
Harvard UniversityHarvard University is a private university located in Cambridge, Massachusetts and a member of the Ivy League. Founded in 1636 by the colonial Massachusetts legislature, Harvard is the oldest institution of higher learning in the United States and currently comprises ten separate academic units...
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 research university located in the Westwood neighborhood of Los Angeles, California, in the United States. It was founded in 1919 and is the second-oldest general-purpose campus in the University of California system...
, 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 and mathematician. 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 in logic.His workon...
. 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 a private university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League and is considered one of the Colonial Colleges....
(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 Peano arithmetic and first-order logic
First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
are 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 — the problem is not decidable....
. The latter result 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 effectively calculable functions by recursion , by mechanical device equivalent to a Turing machine or by use of Church's λ-calculus...
.
- He was the founding editor of the Journal of Symbolic 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. It was introduced by Alonzo Church in 1932 as part of an investigation into the foundations of mathematics...
.
The lambda calculus emerged in his famous 1936 paper showing the existence of an "
undecidable 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 — the problem is not decidable....
". This result preceded
Alan TuringAlan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was influential in the development of computer science and provided an influential formalisation of the concept of the algorithm and computation with the Turing machine...
's famous work on the
halting problemIn computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program, decide whether the program finishes running or will 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 contained on a strip of tape. 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 of a computer. The Turing...
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. Like Fortran, Lisp has changed a great deal...
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
Church's doctoral students were an extraordinarily accomplished lot, 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 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 Eugene Kurtz....
,
Stephen C. KleeneStephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
,
Simon B. Kochen,
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....
, Gary Mar,
Michael O. RabinMichael Oser Rabin is a computer scientist and a recipient of the Turing Award.-Biography:...
,
Nicholas RescherNicholas Rescher is an American philosopher, affiliated for many years with the University of Pittsburgh, where he is currently University Professor of Philosophy and Chairman of the Center for Philosophy of Science. Born in Germany, he came to the United States at the age of nine...
, Hartley Rogers, Jr.,
J. Barkley RosserJohn Barkley Rosser Sr. was an American logician, a student of Alonzo Church, and known for his part in the Church-Rosser theorem, in lambda calculus. He also developed what is now called the Rosser sieve, in number theory. He was later Director of the Army Mathematics Research Center at the...
,
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, 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 influential in the development of computer science and provided an influential formalisation of the concept of the algorithm and computation with the Turing machine...
. See
http://www.math.ucla.edu/~asl/bsl/0104/0104-005.ps.
A more complete list is at
http://genealogy.math.ndsu.nodak.edu/id.php?id=8011 as part of the
Mathematics Genealogy ProjectThe Mathematics Genealogy Project is a web-based database that gives an academic genealogy based on dissertation supervisor. A Ph.D. mathematician's "parent" is her/his doctoral advisor...
.
Books
- Alonzo Church, Introduction to Mathematical Logic (ISBN 978-0691029061)
- Alonzo Church, The Calculi of Lambda-Conversion (ISBN 978-0691083940)
- Alonzo Church, A Bibliography of Symbolic Logic, 1666–1935 (ISBN 978-0821800843)
- C. Anthony Anderson and Michael Zelëny, editors, Logic, Meaning and Computation: Essays in Memory of Alonzo Church (ISBN 978-1402001413)
Sources
- Enderton, Herbert B., Alonzo Church: Life and Work. Introduction to the Collected Works of Alonzo Church, MIT Press, not yet published.
- 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.
External links