The book begins with a transcript of Chaitin's Distinguished Lecture at Carnegie-Mellon University in March 2000 on "a century of controversy over the foundations of mathematics." Cantor's work on infinite sets and the Russell paradox raised serious questions about the mathematical enterprise at the end of the nineteenth century, questions that Hilbert proposed to resolve using formal axiomatics. Hilbert's program ended in defeat with the incompleteness result of Gödel and Turing's analysis of the halting problem. The parallel between these mathematical forms of things that cannot be known, and the physical unknowability of quantum mechanics, led Chaitin to his hypothesis that mathematics is, at base, as random and unknowable as physics.
In the balance of Part 1, Chaitin introduces his LISP dialect and describes how it can be used to explain complex mathematical ideas. The fundamental insight around which AIT is constructed is that the complexity of something is the length of the shortest program that will produce it, and working with a specific computer program permits this concept to be demonstrated concretely. Critical to this approach is the basic concept of a self-delimiting program, one that asks for its bits only as they are needed. This constraint permits an additive definition of information, so that the complexity of a pair of programs is bounded by the sum of their individual complexities.
Part 2 develops the fundamental results of AIT. The first step is to show how an actual self-delimiting Turing machine can be constructed as a set of pairs enumerating programs and their outputs. The key to this construction is a version of the Kraft inequality, from information theory, which permits generating such a set of (program, output) pairs from a list of pairs stating (output, size of program) requirements, as long as the total "algorithmic probability" over all the requirements is less than or equal to 1. This latter quantity, which links computability and complexity to probability, is the probability that a program generated by coin tossing calculates the required output. With these tools, Chaitin leads readers through the proofs of two fundamental results. First, the complexity of an object (the size of the smallest program to compute it) is, within a fixed number of bits, the base-2 log of the inverse of the probability of computing it with a program generated by chance. Second, combining a program for x with a program for getting y from x yields the best possible program for the pair, again within a fixed number of bits.
As the book's title suggests, these concepts are merely the warm-up for Part 3, which uses them to explore the concept of randomness. The first chapter in Part 3 develops Chaitin's definition of randomness: something is random if it is incompressible (if the shortest program to compute it is as long as the result being computed). The final result of this chapter is a proof that the probability is random in this formal sense that a randomly generated program will halt. The rest of Part 3 proves the equivalence of Chaitin's definition of randomness with definitions offered by Martin-Löf and Solovay.
Part 4 looks ahead to opportunities for future work, outlining some unsolved problems and directly challenging readers to get involved in research in this area.
Chaitin's ideas are among the deepest in modern computer science. Thanks to his zeal for exposition, they are also among the most accessible. Like its predecessors, this volume should enjoy a wide readership.
Review by: H. Van Dyke Parunak
[1] Chaitin, G. J. The unknowable. Springer-Verlag, Singapore, 1999.
[2] Chaitin, G. J. The limits of mathematics. Springer-Verlag, Singapore, 1998.