Exploring RANDOMNESS /
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 c...
| Main Author: | |
|---|---|
| Corporate Author: | |
| Format: | eBook |
| Language: | English |
| Published: |
London :
Springer London,
2001.
|
| Series: | Discrete mathematics and theoretical computer science.
|
| Subjects: | |
| Online Access: | Connect to the full text of this electronic book |
Table of Contents:
- Introduction: Historical Introduction. What is LISP? Why do I like it? How to Program my Universal Turing Machine in LISP
- 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. The Basic Result on Relative Complexity
- Randomness: Theoretical Interlude - What is Randomness? My definitions. Proof that Martin-Löf Randomness is Equivalent to Martin-Löf Randomness. Proof that Solovay Randomness is Equivalent to Strong Chaitin Randomness
- Future Work: Extending AIT to the Size of Programs for Computing Infinite Sets and to Computations with Oracles. Postscript - Letter to a Young Reader.