Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995), American mathematician and logician who laid the foundation for theoretical computing. Born in Washington, D.C., he graduated in 1924 and received his doctorate in 1927 from Princeton University, where he taught from 1929 to 1967.

His best known work is the development of the lambda calculus, and his 1936 paper showing the existence of undecidable problems. This work preceded the famous work of his student Alan Turing on the stopping problem which also demonstrated the existence of problems unsolvable by mechanical devices. After reviewing Turing's doctoral thesis, they showed that the lambda calculus and the Turing machine used to express the stopping problem had equal power of expression; they subsequently demonstrated that a variety of alternate mechanical processes for performing computations had equivalent computing power. As a result, the Church-Turing Thesis was postulated.

Among Church's best-known doctoral students are Stephen Kleene, J. Barkley Rosser, Leon Henkin, John George Kemeny, Michael O. Rabin, Dana Scott, Simon Kochen, and Raymond Smullyan.

Church published between 1924 and 1995 papers on Logic, Philosophy, Mathematics and Computation. In his 1936 work An unsolvable problem of elementary number theory Church first formulated what is now known as Church's thesis which is the identification of the vague concept of effective calculability with the precise notion of function. recursive. His article A note on the entscheidungsproblem presented what is now known as Church's theorem: The undecidability of the validity of first-order logic. In 1941 he published his monograph The calculi of lambda-conversion. This work has great influence in the area of theoretical computing.

The lambda calculus influenced the design of the Lisp language, as well as functional programming languages.