Information-theoretic Incompleteness

In this mathematical autobiography, Gregory Chaitin presents a technical survey of his work and a non-technical discussion of its significance. The volume is a companion to the earlier collection of Chaitin’s papers Information, Randomness and Incompleteness also published by World Scientific. The technical survey contains many new results, including a detailed discussion of LISP program size and new versions of Chaitin’s most fundamental information-theoretic incompleteness theorems. The nontechnical part includes the lecture given by Chaitin in Goedel’s classroom at the University of Vienna, a transcript of a BBC TV interview, and articles from the New Scientist , La Recherche , and the Mathematical Intelligencer .