Computer science is a paradox. Intensely practical in its contribution to modern society, it is founded on some of the most abstract intellectual manipulations in the history of human thought. Its foundations include results that seem as destructive of rational thought as its practical manifestations are constructive of economic progress. Chaitin is one of the field's leading theoreticians, and has played a major role in the negative side of this paradox. This slender volume offers a readable account of three major results on the limitations of mathematics: Gödel's incompleteness theorem, Turing's proof of the unsolvability of the halting problem, and Chaitin's own demonstration that one cannot know that one has found the shortest possible program to compute a given function. Each of these formal mathematical results is related to a paradox that had been recognized less formally.
Gödel's theorem is the formalization of the liar's paradox, which grapples with utterances of the form, "This statement is false." Gödel managed to show that any axiomatic system capable of supporting number theory can express a similar utterance (specifically, "This statement is not provable"), thereby showing that such systems are either incomplete or inconsistent. Turing's result derives from Russell's paradox concerning the set of all sets that are not members of themselves. Russell asked whether this set is a member of itself or not. Turing focused his attention on the question of partitioning all programs into those that halt and those that do not. He shows that this question cannot be computed, because if it could, one could construct a program that halts only if it does not halt. Chaitin's work derives from Berry's paradox, exemplified by the expression, "the first natural number that cannot be named in less than fourteen words" (which is in fact a thirteen-word name for this unnameable number). Chaitin's work focuses on the notion of expressing the complexity of something by the length of the shortest program that can compute it, and then showing that this measure is itself not computable.
Chapter 1 is a highly autobiographical survey of these three major results. Chaitin explains the basic ideas informally, and situates them not only in the broader history of mathematics, but in his own intellectual development, beginning with his teenage fascination with Gödel's work. The conclusion of the chapter, echoed in the final chapter as the conclusion of the book, is that mathematics is quasi-empirical, differing from physics in degree, not in kind, and is based on experimentation as much as on abstract thought.
In keeping with this experimental orientation, Chaitin makes his ideas and those of his predecessors precise, not by shrouding them in formal definitions and abstract notation, but by exhibiting simple computer programs whose behaviors mirror the basic ideas in the proof. For this purpose, he employs a simple dialect of LISP. Chapter 2 defines and explains this dialect, for which three different interpreters are available on Chaitin's Web site, and suggests exercises to help the reader gain facility in the language. LISP in general is characterized by simple syntax and precise semantics, and Chaitin's dialect emphasizes these features, making it a formal tool appropriate for highly abstract mathematical exploration. With this tool in hand, each of chapters 3, 4, and 5 introduces a successive paradox.
The heart of Gödel's theorem (and of all three results) is the ability of a formal system to make statements about itself. Chapter 3 begins by exhibiting a self-referential LISP function, specifically, one that reproduces itself when applied to itself. Positing a function "is-unprovable" and applying it to itself in this way yields an instance of Gödel's classical self-defeating statement. This instance, unlike Gödel's original, is immediately transparent, thanks to the economy of LISP's S-expressions.
Chapter 4 demonstrates Turing's halting paradox using the same self-referential trick. Now the self-referential function is one that halts if its argument does not halt, and applying this function to itself provides the desired contradiction.
The nature of self-reference used in Chaitin's theorem, discussed in chapter 5, is different from that in the previous chapters. He exhibits a LISP program B that knows its own length. Under the assumption that a given formal axiomatic system can prove whether an expression is the shortest expression returning a given value, B surveys the theorems provable in that system, and returns the value of an expression only if the formal system purportedly proves that the shortest expression yielding that value is longer than B. Of course, under these conditions, the supposed "shortest expression" is longer than B, which returns the same value. This contradiction invalidates the assumption that a formal axiomatic system can prove that an expression is the shortest possible.
Chapter 6 goes beyond the LISP demonstrations of the previous chapters to sketch out the broader field of algorithmic information theory that Chaitin and others have developed based on the ideas in chapter 5. This highly personal account not only outlines the more important results in the field, but recounts the circumstances under which they were developed and published, arguing for the superiority and priority of the author's results over those produced independently by other researchers. Chapter 7, "Mathematics in the Third Millennium?" steps back from the technical paradoxes of the preceding chapters to reflect on the nature of mathematics. It returns to the claim in the opening chapter that mathematics, far from being a precise abstract science, is quasi-empirical, subject to complications and "messiness" just as are other sciences.
Chaitin's own involvement with these deep ideas began in his youth, and this volume is simple enough to be accessible to high school students. The LISP programs deserve to find their way into undergraduate computer science lectures as concrete demonstrations of otherwise abstract concepts. The volume has no index, but the bibliography spans the range from highly formal original publications to biographies, popularizations, and even works of fiction that capture the feeling of doing mathematics.
Review by: H. Van Dyke Parunak