Alonzo Church

Alonzo Church (14 June 1903—11 August 1995) was an eminent US mathematician and logician with works of major importance in mathematical logic, recursion theory, and in theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, proving the undecidability of the Entscheidungsproblem, Frege–Church ontology, and the Church–Rosser theorem.

In 1936, Church created a method for defining functions called lambda calculus (λ-calculus). Within λ-calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ-computable if the corresponding function on the Church numerals can be represented by a term of the λ-calculus (which is equivalent to using general recursive functions).

In the same 1936, before learning of Church’s work, Alan Turing (Turing arrived at Princeton in 1936 and Alonzo Church was Turing’s Ph.D. Advisor) created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers.

In computability theory, the Church–Turing thesis is a hypothesis (“thesis”) about the nature of computable functions. In simple terms, the Church–Turing thesis states that a function on the natural numbers is computable in an informal sense (i.e., computable by a human being using a pencil-and-paper method, ignoring resource limitations) if and only if it is computable by a Turing machine.

In 1941 Church wrote the monograph The Calculi of Lambda-conversion, which was later useful to others in the development of semantics for programming languages. Today the λ-calculus is a major research topic in theoretical computer science.

Among the many awards that Church received were his election to the American Academy of Arts and Sciences in 1967 and his election to the National Academy of Sciences, and to the British Academy, both in 1978. As one of his colleagues remembered, “Church read everything and forgot nothing”. When asked what made Church a world-class scholar, he had a remarkably simple answer: “He was just smarter than anybody else.”