OBITUARY: Alonzo Church

Click to follow
The Independent Online
Alonzo Church ranks among the creators of two disciplines: mathematical logic and the theory of computation. The list of his 31 doctoral students includes some of the best-known names in logic and the foundations of computing, such as Stephen Kleene, Alan Turing, John Kemeny, Martin Davis, Dana Scott, Raymond Smullyan.

In the early 1930s, Church did three things for which he will surely be remembered in future centuries. First, he devised the lambda calculus, a remarkably simple calculus for studying the nature of mathematical operations. It is now one of the fundamental tools of computer science.

Second, he stated "Church's Thesis", which proposed an exact formalisation for the notion of a class of problems that can be solved by a mechanical method of computation. Since the notion of a mechanical method of computation is vague, this was a surprising proposal. But it is now generally accepted, thanks to the work of Church's students Kleene and Turing, work which led almost directly to John von Neumann's design for the first electronic digital computers.

Third, Church proved (assuming his Thesis) that there is no mechanical procedure for solving all the problems of elementary logic - unlike the problems of elementary arithmetic, which we learn to solve by mechanical methods at school.

The citation for his honorary DSc at Princeton University summarised these achievements as follows: "He defined the central question concerning the boundaries of formal reasoning."

Church's later work, though less revolutionary, shed light on basic issues in logic. He worked on the theory of types (important for functional programing languages). He entered into controversies on the semantics of natural languages, and continued to write on this theme well into his seventies. In 1956 he published a textbook, Introduction to Mathematical Logic, I, which is still widely quoted.

Alonzo Church became an Assistant Professor at Princeton University in 1929, and continued teaching until he finally retired from the University of California at Los Angeles in 1990. (He had moved there in 1967 because the University of Princeton required him to retire at the age of 65.) A teaching career of 61 years is remarkable in itself, but Church made it still more remarkable by his individual style. His student Don Collins has described it as "remorseless lucidity". No detail was too small: everything had to be set out slowly and precisely, in logical order and huge handwriting. Many of his students were inspired by this vision of a truly rational mind. Others found it paradoxical that creative genius could seem so ponderous.

When the Association for Symbolic Logic was founded in 1935, Church became an editor of its journal, the Journal of Symbolic Logic. He continued in charge of the reviews section until 1979, and set what must surely have been the highest standards of objectivity and consistency required by any journal. In one review which I wrote, he refused to allow a sentence saying that the paper under review had enabled another scholar to solve an important problem, on the grounds that later work would not have been available to the author at the time when he wrote the paper.

Less fortunate reviewers remember "The Bomb", a letter which calmly dismantled the ego of any reviewer who was too late sending in his review.

As a teacher and colleague he was good-natured, patient, modest and undemonstrative. When I knew him at UCLA in 1968 it was my first job, but he treated all of us in the department as equals in the search for truth. At staff meetings he might seem to be asleep, but suddenly he would wake up and resolve some quarrel by proposing exactly the right choice of words. It is recorded that he once agreed to pass a questionable graduate student on condition that the student "promise never to write an article on the philosophical significance of Goedel's theorem". He was a giant physically as well as intellectually: when he chaired a meeting at which the speaker went on too long, he would slowly stand up between speaker and audience, and that was that.

Alonzo Church, logician: born Washington DC 14 June 1903; Assistant Professor of Mathematics, Princeton University 1929-39, Associate Professor 1939-47, Professor 1947-61, Professor of Mathematics and Philosophy 1961- 67; Editor, Journal of Symbolic Logic 1936-79; Flint Professor of Philosophy, UCLA 1967-90; married 1925 Mary Kuczinski (died 1976; one son, two daughters); died Hudson, Ohio 11 August 1995.