Alonzo Church was an American mathematician and logician who provided significant innovations in number theory and decision theory, the foundation of computer programming. His most important contributions focus on the degrees of decidability and solvability in logic and mathematics.
Church was born in Washington, D.C., on June 14, 1903, to Samuel Robbins Church and Mildred Hannah Letterman Church. He took his undergraduate degree from Princeton University in 1924. On August 25, 1925, he married Mary Julia Kuczinski. They had three children: Alonzo, Mary Ann, and Mildred Warner. Church completed his Ph.D. in mathematics at Princeton in 1927. After receiving his doctorate he became a fellow at Harvard from 1927 to 1928. He studied in Europe from 1928 to 1929 at the University of Göttingen, a prestigious center for the study of mathematics and physics. He taught mathematics and philosophy at Princeton from 1929 to 1968. Among his Ph.D. students at Princeton was the British mathematician Alan Turing, who during World War II cracked the Nazi's secret code (called Enigma), which significantly contributed to the Allied victory. In 1944 Church published his influential Introduction to Mathematical Logic. Upon his retirement, however, he became professor of philosophy and mathematics at the University of California, where he remained until his second retirement in 1990. Church later moved to Hudson, Ohio, to be near his son. He died in Hudson on August 11, 1995. In addition to his work as a teacher, Church edited the Journal of Symbolic Logic from 1936 to 1979. His wife died in February 1976.
One of the key problems concerning the foundations of mathematics was stated by the German mathematician David Hilbert (1862-1943) when he asked whether the arithmetic is consistent. The belief that formal systems, such as arithmetic, are consistent had been the cornerstone of mathematics for more than 2,000 years, and Hilbert devoted much energy to the task of showing the power of formal systems. The foundational idea of consistent formal systems, crucial to both mathematics and logic, was shattered in 1931 when Kurt Gödel published his epoch-making article "On the Formal Undecidability Thesis of Principia Mathematica and Related Systems." In essence, Gödel demonstrated that proof of consistency cannot be found within a formal system. Indeed, one can look for proof outside the system, perhaps within a larger system, but this still would not solve the problem of inconsistency, because there would be no way of proving that the larger system is consistent. Influenced by Gödel's work, Church provided the proof, in 1936, that elementary quantification theory--the basic method that logicians use to express general statements--is not decidable. This means that in elementary quantification theory there is no method (containing a finite number of steps) of proving a given statement.
For computer programs to run, programmers have to be able to reduce all problems to the kinds of simple binary logical (or "on/off") statements that can be processed by the electronic circuits inside the computer. For a problem to be solvable by a computer, it must be possible to break it down into an operational set of rules and terms. Next it must be possible to apply these rules recursively--that is repeatedly--to the problem until it is solved in terms of the existing set of rules. In short, a computer's binary circuits can only solve a problem under three conditions: 1) if the problem can be expressed as a meaningful set of rules (i.e., meaningful to the computer); 2) if the result of each step is also meaningful in terms of the computer's predefined set of rules; 3) if the computer's set of rules can be applied repeatedly to the problem. For example, in a simple computer program that does only addition or subtraction, it must be possible for a small number (e.g., 1) to be repeatedly added to or subtracted from a larger number (e.g., 100) to get some result, say 10 or 10,000. If any of the three conditions mentioned above is absent, then a computer program cannot solve the problem.
Church's contribution to the foundation of computer programming is that he discovered--as did Alan Turing and Emil Post simultaneously and independently--the importance of recursiveness in solving logical problems. That is, for calculations to take place, some actions (e.g., adding or subtracting) have to be repeated a certain number of times. In 1936, the same year he shook the foundations of logic, Church formulated the thesis that every intuitively calculable function is recursive. This thesis (which is often called the Church-Turing thesis) states that a function is computable or calculable if it is recursive. That is, the idea of recursiveness (repeatability) is tightly bound up with computability. Church's thesis is important because the repetition of a simple action can result in significant changes. It also means that one simple action can be useful over a broad range of problems, and at different levels of a problem.
Church's contributions to decidability theory earned him many honors, including induction into the National Academy of Science and the American Academy of Arts and Sciences. He received honorary doctorates from Case Western Reserve University in 1969, Princeton University in 1985, and the State University of New York at Buffalo in 1990.
Church died on August 11, 1995, in Hudson, Ohio.
This is the complete article, containing 865 words
(approx. 3 pages at 300 words per page).
