Skip to main content Skip to Search Box
Summary Article: VI.89 Alonzo Church
from The Princeton Companion to Mathematics

Church’s career was spent almost entirely at Princeton. Having studied there, he returned, after spending time in Harvard, Göttingen, and Amsterdam, to take up a position as an assistant professor in 1929. He became Professor of Philosophy and Mathematics in 1961, a position he held until his retirement in 1967. He then moved to the University of California at Los Angeles, where he was Kent Professor of Philosophy and Professor of Mathematics until he retired (again) in 1990.

Princeton became an important center for logic during the 1930s: von neumann [VI.91] arrived at the beginning of the decade; gödel [VI.92] visited in 1933 and 1935 before moving there permanently in 1940; and from September 1936 turing [VI.94] spent two years there as a graduate student, completing his Ph.D. with Church.

In 1936 Church made two profound contributions to the theory of logic. The first, which appeared in a paper entitled “An unsolvable problem in elementary number theory,” is what is now known as Church’s thesis: the proposal to identify the vague intuitive notion of effective calculability with the precise notion of a recursive function [II.4 §3.2.1]. It quickly transpired that Church’s definition of a recursive function was equivalent to Turing’s definition of computable functions. At the end of 1936, Turing, who had been working with analogous ideas in an entirely different way, published his famous paper “On computable numbers,” which contained the result that every function that is naturally regarded as computable is computable by a turing machines [IV.20 §1.1]. Church’s thesis is therefore often known as the Church–Turing thesis.

The second of Church’s contributions is what is now known as Church’s theorem. In a short paper published in the first issue of The Journal of Symbolic Logic, Church showed that it is impossible to decide algorithmically whether statements in arithmetic are true or false. It follows that a general solution to the Entscheidungsproblem (decision problem) does not exist; equivalently, first-order logic is undecidable (see the insolubility of the halting problem [V.20]). This result is also known as the Church–Turing theorem because Turing independently (and in the paper referred to above) proved the same result. In achieving this result, both Church and Turing were strongly influenced by gödel’s incompleteness theorem [V.15].

Copyright © 2010 by Princeton University Press

Related Articles

Full text Article Church, Alonzo
Biographical Dictionary of 20th Century Philosophers

American, b: 14 June 1903, Washington, DC. Cat: Mathematical logician. Ints: Logic; philosophy of language. Educ: 1924, Princeton...

Full text Article Computability and Its Limitations
Computing: A Historical and Technical Perspective

Until the mid 1930s the notion of computability had not yet been mathematically well established, which is natural since the first electronic comput

Encyclopedia of Computer Science

One of this century's major intellectual discoveries is that there are some perfectly precise problems that can never be solved. This is a...

See more from Credo