Exploring Randomness

The book is devoted to a Lisp formalism for exploring the basic ideas, concepts and results on program-size complexity and random sequences. The book contains a wealth of exercises, ranging from the ‘mathematical equivalent of finger warm-ups for pianists’ to substantial programming projects, from open questions to questions the author cannot even formulate. Highly recommended to anyone interested in understanding algorithmic information theory through programming.

This book uses LISP to explore the theory of randomness, called algorithmic information theory (AIT). This is the third of Chaitin’s book. The common theme of the books is the study of H(x), the size in bits of the smallest program for calculating x. Each book has a different emphasis. This book gives a detailed discussion of the metamathematical implications of these ideas and presents the technical core of Chaitin’s algorithmic theory.