Alonzo Church (1903-1995) was a mathematician who contributed greatly to the study of computability theory and symbolic logic. His research mostly focused on computability theory, and he provided two major discoveries that revolutionized the field.
Alonzo Church was born in Washington, D.C. in 1903. He was very adept at mathematics as a youth and eventually went on to study mathematics at Göttingen University and later at the University of Amsterdam, where he received his Ph.D. He also studied at Harvard as a National Research Fellow from 1927 to 1929. He joined the faculty at Princeton University in 1929 and there began to study mathematical logic and computability theory.
His first major discovery came in the early 1930s, when he developed the concept of lambda-calculus, a method of describing computability, and was able to demonstrate that for a large number of formal systems, even simple arithmetic, there are no effective decision procedures for the provable well-formed formulae. In essence, he proved that it is impossible to build a computing machine that can identify and comprehend simple arithmetic (or any other formal system of logic) without being hard-coded with the rules of the arithmetic. This paper, a worthwhile read for anyone interested in the field, is named An unsolvable problem in elementary number theory and appears in the American Journal of Mathematics volume 58, pages 345-363.
His second major discovery came in the late 1930s, when he stated what would become known as the Church-Turing thesis for the first time. This thesis states that given any problem that can be solved with an effective algorithm, there is some sort of automata that can solve it; later, when Turing developed the concept of Turing machines which could duplicate any other sort of automata, the thesis became restated to say that there is a Turing machine that can solve any problem that can be solved with an algorithm. These two discoveries are a major part of the foundation of the theory of computation and lay the groundwork, even today, for much of the theory of computer science.
In addition to his own research, Church also taught many well-known students in the area of computability theory. Among these students were Stephen Cole Kleene and Alan Turing, both of whom Church had as doctoral students, and both of who would become giants in the field. In 1944, Church published the landmark textbook in the field, Introduction to Mathematical Logic, which even today serves as a textbook for mathematical logic and computability theory classes.
In 1967, Church left Princeton after thirty-eight years and moved on to UCLA, where he continued to do research and publish papers until his retirement in 1990. Even in retirement, though, he still continued to publish papers until 1994, well after his 90th birthday. He passed away in 1995, leaving behind a legacy of computability theory.