Alonzo Church

1903-1995

American Mathematician

Like his more famous pupil Alan Turing (1912-1954), Alonzo Church contributed significantly to the foundations of computer science. He is credited, along with Turing, with formulating a key principle concerning computer logic involving recursion, or the recurring repetition of a given operation. His other principal achievement was Church's theorem (1936), which maintains that there is no decision procedure—i.e., no fail-safe method for ensuring that one will always reach correct conclusions—in mathematics.

Born in Washington, D.C., on June 14, 1903, Church was the son of Samuel and Mildred Letterman Church. He studied at Princeton University, where in 1924 he received his B.A. in mathematics. On August 25, 1925, Church married Mary Julia Kuczinski, with whom he had three children: Alonzo, Mary Ann, and Mildred.

Church earned his doctorate at Princeton in 1927, after which he spent a year as a fellow at Harvard. He followed this with a year of study at the prestigious University of Göttingen in Germany, then returned to the United States to take a position as professor of mathematics at Princeton in 1929. Church would remain at Princeton for nearly four decades, during which time he taught a number of important students—including Turing, then studying for his Ph.D., who would later go on to a brilliant if tragic career. (Turing, whose hypothesized "Turing machine" provided an early theoretical model for the computer, committed suicide in 1954 after being arrested for homosexuality, then a punishable offense in Great Britain.)

During his early years at Princeton, Church approached the question of decidability, first notably raised by German mathematician David Hilbert (1862-1943). A problem in logic, decidability revolves around the question of whether there exists a method that could in principle be used to test any proposition and thereby ensure a correct answer as to that proposition's truth or falsehood. Hilbert had believed decidability to be possible, but Church showed in "An Unsolvable Problem of Elementary Number Theory," which he published in the American Journal of Mathematics in 1936, that no general method could be used for all possible assertions. In so doing, he extended the investigations of Kurt Gödel (1906-1978) regarding the incompleteness of mathematics, or indeed of any system of thought.

Also in the 1930s, Church undertook work that would prove significant in the development of a machine that did not yet exist: the computer. He discovered that in order for a problem to be calculable, it must admit to recursiveness. In other words, for the problem (100 - 50) to be solvable, it must be capable of being broken down into a recursive series, as indeed it is: 100 - 1, 99 - 1; 98 - 1, and so on. This 1 calculus, as it came to be known, would later provide the basis for the operation of computer problem-solving, which must be broken down into recursive rules and terms.

In 1967, Church made a big move, from Princeton on the East Coast to the University of California at Los Angeles on the West. At that point he was already 64, an age when most people prepare for retirement; however, he continued teaching at Los Angeles until 1990, when he was 87 years old. His wife died in 1976. A number of honors attended Church's career, among them membership in the American Academy of Arts and Sciences and the National Academy of Science. He died on August 11, 1995, in Hudson, Ohio.

JUDSON KNIGHT