Exploring RANDOMNESS

In The Unknowable I use LISP to compare my work on incompleteness with that of G6del and Turing, and in The Limits of Mathematics I use LISP to discuss my work on incompleteness in more detail. In this book we'll use LISP to explore my theory of randomness, called algorithmic information theory (AIT). And when I say "explore" I mean it! This book is full of exercises for the reader, ranging from the mathematical equivalent oftrivial "fin­ ger warm-ups" for pianists, to substantial programming projects, to questions I can formulate precisely but don't know how to answer, to questions that I don't even know how to formulate precisely! I really want you to follow my example and hike offinto the wilder­ ness and explore AIT on your own! You can stay on the trails that I've blazed and explore the well-known part of AIT, or you can go off on your own and become a fellow researcher, a colleague of mine! One way or another, the goal of this book is to make you into a participant, not a passive observer of AlT. In other words, it's too easy to just listen to a recording of AIT, that's not the way to learn music.

I Introduction.- Historical introduction—A century of controversy over the foundations of mathematics.- What is LISP? Why do I like it?.- How to program my universal Turing machine in LISP.- II Program Size.- A self-delimiting Turing machine considered as a set of (program, output) pairs.- How to construct self-delimiting Turing machines: the Kraft inequality.- The connection between program-size complexity and algorithmic probability: H(x) = ? log2P(x) +O(1). Occam’s razor: there are few minimum-size programs.- The basic result on relative complexity: H(y?x) = H(x,y)-H(x)+O(1).- III Randomness.- Theoretical interlude—What is randomness? My definitions.- Proof that Martin-Löf randomness is equivalent to Chaitin randomness.- Proof that Solovay randomness is equivalent to Martin-Löf randomness.- Proof that Solovay randomness is equivalent to strong Chaitin randomness.- IV Future Work.- Extending AIT to the size of programs for computing infinite sets and to computations with oracles.- Postscript—Letter to a daring young reader.