Exploring Randomness

by Chaitin, Gregory J.

• ISBN13: 9781852334178
• ISBN10: 1852334177
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Springer-Verlag New York Inc

Summary

This essential companion volume to CHAITIN's highly successful books The Unknowable and The Limits of Mathematics, also published by Springer, presents the technical core of his theory of program-size complexity, also known as algorithmic information theory. (The two previous volumes are more concerned with applications to meta-mathematics.) LISP is used to present the key algorithms and to enable computer users to interact with the author's proofs and discover for themselves how they work. The LISP code for this book is available at the author's Web site together with a Java applet LISP interpreter: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ait/"No one has looked deeper and farther into the abyss of randomness and its role in mathematics than Greg Chaitin. This book tells you everything he's seen. Don't miss it."John Casti, Santa Fe Institute, Author of "Goedel: A Life of Logic"

Table of Contents

I Introduction	1	(60)
Historical introduction---A century of controversy over the foundations of mathematics	3	(26)
What is LISP? Why do I like it?	29	(16)
How to program my universal Turing machine in LISP	45	(16)
II Program Size	61	(48)
A self-delimiting Turing machine considered as a set of (program, output) pairs	63	(10)
How to construct self-delimiting Turing machines: the Kraft inequality	73	(12)
The connection between program-size complexity and algorithmic probability: H(x) = -- log2 P(x) + O(1). Occam's razor: there are few minimum-size programs	85	(10)
The basic result on relative complexity: H(y\x) = H(x,y) -- H(x) + O(1)	95	(14)
III Randomness	109	(38)
Theoretical interlude---What is randomness? My definitions	111	(18)
Proof that Martin-Lof randomness is equivalent to Chaitin randomness	129	(10)
Proof that Solovay randomness is equivalent to Martin-Lof randomness	139	(4)
Proof that Solovay randomness is equivalent to strong Chaitin randomness	143	(4)
IV Future Work	147	(14)
Extending AIT to the size of programs for computing infinite sets and to computations with oracles	149	(12)
Postscript---Letter to a daring young reader	161