Alonzo Church was an American mathematician and logician who provided significant innovations in number theoryand decision theory, the foundation of computerprogramming. His most important contributions focus on the degrees of decidabilityand solvabilityin 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 was 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 was to crack the German's World War II secret code, called Enigma, which significantly contributed to the Allied victory over Nazi Germany. 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 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.
A very private person, Church led a quiet life. As Andrew Hodges said in his biography of Alan Turing (Church's famed student who killed himself in 1954 after being arrested on homosexual charges), Church "[is] a retiring man himself, not given to a great deal of discussion."
Addressing the Problem of Decidability
One of the key problems concerning 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.
Laying the Foundations of Computer Programming
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 addition or subtraction computer program, 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 these 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 Postsimultaneously and independently--the importance of recursivenessin 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. (which is often called the Church-Turing thesis) is 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.
This is the complete article, containing 904 words
(approx. 3 pages at 300 words per page).
