(Quoted without permission from 95Sep05 NYT)
Alonzo Church, an eminent contributor to mathematical logic and teacher of a generation of American logicians, died in Hudson, Ohio on Aug. 11. He was 92.
Dr. Church's principal achievements lay in extending the work of Kurt Godel on the foundations of mathematics in a direction that bears on modern philosophy and computer science. "If you ask who is the greatest logician of this century, no question it's Godel, but Church was really pre-eminent among American logicians," said Simon B. Kochen, professor of mathematics at Princeton University.
Born in Washington in 1903, Dr Church spent most of his professional career at Princeton, where he recieved his Ph.D. in 1927. Two of his most important contributions to mathematical logic are known as Church's thesis and Churche's theorem.
Both can be explained in reference to Godel's incompleteness theorem, a cornerstone of modern logic. Godel, a young Czech mathematician in Vienna, showed in 1931 that any consistent system of formal logic powerful enough to express the truths of arithmetic must be incomplete, in the sense that it will contain statements that are true but cannot be proved or disproved using the system itself. This dealt a fatal blow to the program proposed by David Hilbert to develop a method for determining the truth or falsity of any statement in formal logic, and hence of any mathematical statement, however complex.
Dr. Church's thesis bears on the question of what is computable by a modern digital computer. His thesis holds that computable functions are in fact the same as what logicians call recursive functions, a notion used by Godel in the proof of his incompleteness theorem.
Although many other definitions of computable functions have been offered since, all have turned out to be the same as recursive functions, just as Dr. Church supposed. Independently, Alan Turing, the English mathematician, proposed a more direct but equivalent definition of computability in the form of a theoretical computing device known as a Turing machine.
Dr. Church's theorem applies to the nature of a branch of logic known as predicate calculus. Just as Godel's incompleteness theorem showed there is no algorithm, or decision procedure, that will determine whether a statement in arithmetic is provable in arithmetic, Dr Church showed there is also no such algorithm in predicate calculus.
Dr. Church's work was inportant in the foundation of computer science. He was also influential as a teacher, including among his students such eminent logicians as Stephen C. Kleene, J. Barkley Rosser and Turing.
Besides training a generation of logicians, Dr. Church edited The Journal of Symbolic Logic, for many years the field's leading publication.
He was a quiet and very precise person. Dr. Kochen, a former student of his, recalled that the first time he attended one of Dr. Church's lecture, Dr. Church "went up to the blackboard, took an eraser and moved it up and down in vertical strokes while humming to himself," adding: "Then he went over the whole blackboard again with horizontal strokes, still humming. I realize now he was just thinking about what he was going to say."
Dr. Church retired from Princeton in 1968 and moved to the University of California at Los Angeles, where he was professor of philosophy and mathematics until 1990. He then move to Hudson, Ohio, to live near his son, Alonzo Church Jr.
His wife, Mary Julia Kuczinksi, died in 1976. In addition to his son, he is survived by two daughters, Mary ann Addison and Mildred Dandridge.