Copyright ©1998-2010 Glenn Fleishman. Send in your comments. Bibliographic information on isbn.nu licensed from Baker & Taylor. Contact them for corrections and licensing, or read more about our data.
Tables of Contents for Exploring Randomness
Chapter/Section Title
Page #
Page Count
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