Exploring RANDOMNESS

G J Chaitin, IBM Research

Published by Springer-Verlag London, 2001, x + 164 pages, hardcover, ISBN 1-85233-417-7. Order from Springer-Verlag, Amazon, Barnes & Noble. Reviewed in J Sci Expl, AMS Notices, Folha de S. Paulo, Comp Rev, New Scientist.

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.

``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 Gödel: A Life of Logic

``The Limits of Mathematics contains unconventional, new and challenging reading at all levels, laymen and experts alike, the only prerequisite being the willingness to question and, if necessary, abandon long-held beliefs and prejudices.''
--- Karl Svozil, Complexity magazine

``According to Gregory Chaitin, `some mathematical statements are true for no reason, they're true by accident'. The Unknowable is his extremely readable exposition of the randomness at the heart of arithmetic.''
--- Marcus Chown, New Scientist, December 1999

``[The Unknowable] presents three milestone achievements in a clear, understandable, hands-on way.''
--- Cristian S. Calude, Mathematical Reviews

Go to the LISP interpreter Web page and use cut and paste to enter and run the LISP source code that's given below.

CONTENTS

• 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
  source, run

• A self-delimiting Turing machine considered as a set of (program, output) pairs
  source, run

• How to construct self-delimiting Turing machines: the Kraft inequality
  source, run

• The connection between program-size complexity and algorithmic probability: H(x) = − log₂ P(x) + O(1).
  Occam's razor: there are few minimum-size programs
  source, run

• The basic result on relative complexity: H(y|x) = H(x, y) − H(x) + O(1)
  source, run, source, run

• Theoretical interlude---What is randomness? My definitions

• Proof that Martin-Löf randomness is equivalent to Chaitin randomness
  source, run, source, run

• Proof that Solovay randomness is equivalent to Martin-Löf randomness
  source, run

• Proof that Solovay randomness is equivalent to strong Chaitin randomness
  source, run, source, run

ERRATA

1. Page 40, lines 9-10: "has a very permissive semantics" should read "has very permissive semantics".

2. Page 73, next to bottom line: "That it!" should read "That's it!".

3. Page 75, bottom line: "lists of assignments" should read "lists of requirements".

4. Page 88, above 2nd displayed equation: "depending or whether or not" should read "depending on whether or not".

5. Page 144, last paragraph, complement of strong Chaitin randomness is wrong. It should read:

   "Let's suppose that the infinite binary sequence r isn't strong Chaitin random. In other words, that there is a k for which there are infinitely many n-bit prefixes of r such that..."

6. Page 116, top half of page, proof in brackets [...] that if α, β are n-bit strings, then H(α:β) ≥ H(n) − c is wrong. It should read:

   [Why must two n-bit strings α, β always have mutual information H(α:β) ≥ H(n) − c? Well,

   H(α:β) = H(α) + H(β) − H(α,β)

   = (H(n) + H(α|n)) + (H(n) + H(β|n)) − (H(n) + H(α,β|n)) + O(1)

   = H(n) + H(α|n) + H(β|n) − H(α,β|n) + O(1).

   But obviously

   H(α,β|n) ≤ H(α|n) + H(β|n) + c'

   (relativised subadditivity). So

   H(α:β) ≥ H(n) − c'',

   which was to be proved.]