Church, Alonzo

Church, Alonzo

(1903–1995) American

Mathematician

Born in Washington, D.C., mathematician and logician Alonzo Church made seminal contributions to the funda-mental theory of computation. Church was mentored by noted geometer Oswald Veblen and graduated from Prince-ton with an A.B. in mathematics in 1924. Veblen encouraged Church to devote his graduate thesis to the investiga-tion of the fundamental problem of computability. At the time, mathematician David Hilbert and his followers were attempting to create a formal way to express mathematical propositions.

In 1927, Church received his Ph.D. from Princeton for a dissertation on the axiom of choice in set theory. During the 1930s, Church developed the lambda calculus, which provided rules for substituting bound variables in generat-ing mathematical functions. The Church thesis (also called the Church-Turing thesis, because Alan Turing [see Tur-ing, Alan] approached the same conclusion from a differ-ent angle) stated that every calculable function in number theory could be defined in lambda calculus and was also computable in Turing’s sense (see computability and com-plexity). This provided the theoretical confidence that given appropriate technology, computers could tackle a variety of problems reliably. At the same time, another of Church’s achievements, the Church theorem, proved that there were theorems that could not be proven by any computer.

Church’s lambda calculus became important for the design and verification of computer languages, and the lisp language in particular was based on lambda expressions. Computer scientists working with problems in list pro-cessing and the use of recursion also have owed much to Church’s pioneering work.

Church taught at Princeton for many years. In 1961, he received the title of Professor of Mathematics and Phi-losophy. In 1967, he took the same position at UCLA, where he was active until 1990. He received numerous honorary degrees, and in 1990 an international symposium was held in his honor at the State University of New York at Buffalo.