- Algorithmic Information Theory.
- Information-Theoretic Incompleteness.
- Meta Math!
- The Limits of Mathematics—A course on information theory and the limits of formal reasoning.
- From Philosophy to Program Size.
I own “Meta Math!“. I bought it by chance. While in the bookstore, I opened it and stumbled upon LISP code. This is a really nice book. It is a personal log of Chaitin‘s career, an introduction to Kolmogorov complexity0 (which was independently invented by Chaitin too), algorithmic information theory, thinking about randomness (and in a way first presented to me years ago by a long time friend), LISP1, useful comments on NKS2, Polya‘s “How to Solve It!” and an introduction to the thought of Leibniz3.
Of course the book has irritating parts: Having invented a field independently of Kolmogorov, somehow puts you in the shadow of the man and Chaitin constantly tries to get out of the shadow and stand not on the shoulders of Turing and Goedel but next to them (when in fact such effort is not needed).
I loved the book4. It is the kind of book that reminds you why you loved Mathematics. Even Chaitin’s personal effort to stress the importance of his work (that annoys many) contributes to this. For he unquestionably loves Mathematics.
(Must make time and read “The Limits of Mathematics”; Time there is not…)
 – More about it at “An introduction to Kolmogorov complexity“.
 – Link to the Lisp interpreter that Chaitin has developed for his needs.
 – See also this presentation on NKS by S. Wolfram.
 – An essay on Leibniz by Chaitin.
 – I also loved “Title: Algorithmic information theory: Some recollections“.