I could write a very short review of Algorithmic Information Theory. Its aim is the proof of one theorem, Theorem D of chapter 8. First, some definitions are needed. An exponential Diophantine expression is built up from non-negative integer variables and non-negative integer constants using only addition, multiplication, and exponentiation. An exponential Diophantine equation is an equality L = R between two exponential Diophantine expressions. If L(n,x1, . . . ,xm) = R(n,x:- 0I1, . . . ,xm) is an exponential Diophantine equation, we set &ohgr;n = 1 if the number of solutions is infinite and &ohgr;n = 0 if this number is finite. Then the key theorem of this book exhibits a Diophantine exponential equation L(n,x1,x2, . . . ,xm) = R- (x,x1, . . . ,xm) such that &ohgr;n is a random sequence.
But what is a random sequence? In fact, randomness, a domain in which Chaitin has made major contributions, is the true core of the book.
The book is in two almost equal parts. The first is on computation, using a pure Lisp approach; the second is on randomness, with a proof of the equivalence of the definitions of Martin-Löf, Solovay, Chaitin, and Schnorr.
That pure Lisp may be taken as a foundation of computation theory is a well-known fact that is often proved through an implicit use of Church’s Thesis. No such trick is used in this book. The author starts with Lisp register machines, that is, register machines that operate in a canonical way on lists, instead of on natural numbers as in most register machines, and shows how to code (in Gödel style) the basic instructions by exponential Diophantine expressions. This is the subject of chapter 2, which ends with a terrific example. The author takes some time with the computer and exhibits an exponential Diophantine equation, each member of which is two pages long, with the two parameters input A and output B. The equation has exactly one solution if and only if output B is the character string reversal of input A. Behind the challenge one finds the weak Matijasevic which ensures the coding of recursively enumerable sets by exponential Diophantine equations in a more convenient form than by usual Diophantine equations.
Chapter 3 presents a version of pure Lisp. Caution: for the needs of the arithmetization of the language, the author has chosen to use new symbols (such as :6WWm), which are obviously generalized letters, instead of the well-established Lisp acronyms (such as CAR). The result is somewhat misleading. Realistically, the author says, “initially the material will seem completely incomprehensible,” and I hope that he is not too optimistic when he adds, “but all of a sudden the pieces will snap together into a coherent whole.”
In chapter 4 the author gives a Lisp interpreter for his Lisp idiom. Mathematically, he builds a universal machine. But the chapter is much too short. The reader will find an unexplained EVAL program and its arithmetization in the form of a four-page exponential Diophantine equation. Without a good knowledge of what a universal machine is and what a classical Lisp interpreter is, the reader will certainly give up.
With part 2, the author goes into randomness. For a long time, the characterization of true random sequences has been a challenge for mathematicians; the major opponents of Kolmogorov axiomatization of the calculus of probabilities have argued that such an approach gives no answer to the question. It was only in 1966 that Martin-Löf suggested a new definition that was acknowledged as suitable. And later on very different approaches have led to the same random sequences. One approach, by Chaitin himself, uses the theory of information; one by Solovay issues from his well-known model of set theory, in which each of the subsets of R is measurable. The equivalence of these definitions is of outstanding importance: it may be seen as a counterpart of the Church Thesis. And it is the subject of chapter 7 of the present book.
How can one give an example of such a random sequence? A major theorem of Chaitin’s insures that the base two expansion of the halting probability &OHgr; of a universal machine is such a random sequence. The reader will find a more concrete definition of &OHgr; via program complexity in chapters 5 and 6, leading to the proof of randomness in chapter 7. Then the key theorem of the book, quoted at the beginning, is proven by translating the definition of &OHgr; as the halting probability of a universal machine coded by an exponential Diophantine equation. In short, this second part establishes randomness on a very firm basis.
In its content as well as in its writing, the book is essentially a research monograph. Proofs, though complete (at least in the second part), are often shortened, and some definitions are not as precisely stated as a nonspecialist reader might hope (this is the case for &OHgr;). And the reader will miss the presence of an index. But this weakness must be forgotten if the reader wants the essential contribution, which is currently the best analysis of the deep concept of randomness.
