Exploring RANDOMNESS

Chapter 1 Historical introduction — A century of controversy over the foundations of mathematics

Chapter 2 What is LISP? Why do I like it?

Chapter 4 A self-delimiting Turing machine considered as a set of (program, output) pairs

Chapter 5 How to construct self-delimiting Turing machines: the Kraft inequality

Chapter 6 The connection between program-size complexity and algorithmic probability: H(x) =-log 2 P(x) + O (1). Occam’s razor: there are few minimum-size programs

Chapter 7 The basic result on relative complexity: H(y∣x)=H(x,y)-H(x)+O(1)

Chapter 8 Theoretical interlude—What is randomness? My definitions

Chapter 9 Proof that Martin-Löf randomness is equivalent to Chaitin randomness

Chapter 10 Proof that Solovay randomness is equivalent to Martin-Löf randomness

Chapter 11 Proof that Solovay randomness is equivalent to strong Chaitin randomness

Chapter 12 Extending AIT to the size of programs for computing infinite sets and to computations with oracles

Chapter 13 Postscript—Letter to a daring young reader