search for books and compare prices
Tables of Contents for Information and Randomness
Chapter/Section Title
Page #
Page Count
Mathematical Background
1
20
Prerequisites
1
3
Computability Theory
4
2
Topology
6
2
Probability Theory
8
11
Exercises and Problems
19
2
Noiseless Coding
21
12
Prefix-free Sets
21
3
Instantaneous Coding
24
6
Exercises and Problems
30
2
History of Results
32
1
Program-size
33
20
An Example
33
1
Computer and Complexities
34
9
Algorithmic Properties of Complexities
43
2
Quantitative Estimates
45
2
Hating Probabilities
47
2
Exercises and Problems
49
3
History of Results
52
1
Computably Enumerable Instantaneous Codes
53
42
The Kraft-Chaitin Theorem
53
7
Relativized Complexities and Probabilities
60
10
Speed-up Theorem
70
4
Algorithmic Coding Theorem
74
11
Binary vs Non-binary Coding (1)
85
4
Exercises and Problems
89
2
History of Results
91
4
Random Strings
95
52
An Empirical Analysis
95
7
Chaitin's Definition of Random Strings
102
5
Relating Complexities K and H
107
2
A Statistical Analysis
109
10
A Computational Analysis
119
4
Borel Normality
123
8
Extensions of Random Strings
131
5
Binary vs Non-binary Coding (2)
136
4
Exercises and Problems
140
5
History of Results
145
2
Random Sequences
147
90
From Random Strings to Random Sequences
147
11
The Definition of Random Sequences
158
11
Characterizations of Random Sequences
169
15
Properties of Random Sequences
184
20
The Reducibility Theorem
204
25
The Randomness Hypothesis
229
2
Exercises and Problems
231
2
History of Results
233
4
Computably Enumerable Random Reals
237
78
Chaitin's Omega Number
237
3
Is Randomnes Base Invariant?
240
13
Most Reals Obey No Probability Laws
253
7
Computable and Uncomputable Reals
260
11
Computably Enumerable Reals, Domination and Degrees
271
23
A Characterization of Computably Enumerable Random Reals
294
8
Degree-theoretic Properties of Computably Enumerable Random Reals
302
8
Exercises and Problems
310
3
History of Results
313
2
Randomness and Incompleteness
315
46
The Incompleteness Phenomenon
315
5
Information-theoretic Incompleteness (1)
320
4
Information-theoretic Incompleteness (2)
324
4
Information-theoretic Incompleteness (3)
328
4
Coding Mathematical Knowledge
332
3
Finitely Refutable Mathematical Problems
335
8
Computing 64 Bits of a Computably Enumerable Random Real
343
12
Turing's Barrier Revisited
355
3
History of Results
358
3
Applications
361
54
The Infinity of Primes
361
1
The Undecidability of the Halting Problem
362
1
Counting as a Source of Randomness
363
3
Randomness and Chaos
366
1
Randomness and Cellular Automata
367
16
Random Sequences of Reals and Riemann's Zeta-function
383
6
Probabilistic Algorithms
389
4
Structural Complexity
393
5
What Is Life?
398
7
Randomness in Physics
405
4
Metaphysical Themes
409
6
Open Problems
415
4
Bibliography
419
36
Notation Index
455
2
Subject Index
457
4
Name Index
461