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...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
London
Springer London
2001, 2001
|
| Edition: | 1st ed. 2001 |
| Series: | Discrete Mathematics and Theoretical Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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