Contents -- Preface -- Acknowledgments -- PART I Stochastic Randomness and Probabilistic Deliberations -- Chapter 1 Is Randomness Necessary? -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T YET KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- Chapter 2 Probability is a Lot of Logic at Once: If You Don't Know Which One to Pick, Take 'em All -- HOW I GOT INTO IT -- 2.1. "Probability Doesn't Exist" -- 2.2. "Hot and Cold" is the Only Game in Town -- 2.3. Maximum Entropy was Easy -- Now, How about Least Action? -- 2.4. Quantum Mechanics: Mystery, No Problem, or Sour Grapes? -- References -- Chapter 3 Statistical Testing of Randomness: New and Old Procedures -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- 3.1. Testing Block Ciphers: Statistical Theory and Common Sense -- 3.2. P-values, One-sided Alternatives versus Two-sided Alternatives and χ2-tests -- WHAT HAVE WE LEARNED: STATISTICAL TESTS WHICH WORK WELL AND SOME WHICH DO NOT -- 3.3. Tests based on the Properties of a Random Walk -- 3.4. Discrete Fourier Transform (Spectral) Test -- 3.5. Non-overlapping and Overlapping Template Matchings -- WHAT WE DO NOT KNOW YET: TESTS BASED ON PATTERNS, PERIODIC OR NOT -- 3.6. Tests of Randomness Based on the Number of Missing Words -- 3.7. Testing Randomness via Words with a Given Frequency -- WHAT ARE THE MOST IMPORTANT OPEN PROBLEMS: DATA COMPRESSION AND RANDOMNESS TESTING -- 3.8. Linear Complexity for Testing Randomness -- 3.9. Tests based on Data Compression -- WHAT ARE THE PROSPECTS FOR PROGRESS: CONCLUDING REMARKS -- References -- Chapter 4 Scatter and Regularity Imply Benford's Law... and More -- WHAT DREW US TO THE STUDY OF THE APPARENT (AWKWARD) RANDOMNESS OF BENFORD'S LAW -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW.

4.1. Scatter and Regularity: A Key to Benford -- THE PROSPECTS FOR PROGRESS -- 4.2. Conclusions -- References -- PART II Randomness and Computation in Connection to the Physical World -- Chapter 5 Some Bridging Results and Challenges in Classical, Quantum and Computational Randomness -- WHAT DREW US TO THE STUDY OF COMPUTATION AND RANDOMNESS -- 5.1. Physical Randomness (Classical) -- 5.2. Physical Randomness (Quantum) -- 5.3. Algorithmic Randomness -- 5.4. Computer Science Randomness -- 5.5. Biology -- WHAT WE HAVE LEARNED -- 5.6. Physical Randomness (Classical) -- 5.7. Physical Randomness (Quantum) -- 5.8. Algorithmic Randomness -- 5.9. Randomness in Computer Science -- 5.10. Biology -- WHAT ARE THE MOST IMPORTANT OPEN PROBLEMS IN THE FIELD? -- 5.11. Algorithmic Randomness -- 5.12. Computer Science -- 5.13. Biology -- 5.14. Quantum Mechanics -- WHAT ARE THE PROSPECTS FOR PROGRESS? -- 5.15. Quantum Randomnesses -- 5.16. Pseudo-randomness and Algorithmic Randomness -- 5.17. Computer Science -- 5.18. Extended Criticality in Biology -- 5.19. Comparison -- References -- Chapter 6 Metaphysics, Metamathematics and Metabiology -- Introduction -- 6.1. Weyl, Leibniz, Complexity and the Principle of Sufficient Reason -- 6.2. What is a Scientific Theory? -- 6.3. Finding Elegant Programs -- 6.4. What is a Formal Axiomatic Theory? -- 6.5. Why Can't You Prove that a Program is Elegant? -- 6.6. Farewell to Reason: The Halting Probability Ω -- 6.7. Adding New Axioms: Quasi-empirical Mathematics -- 6.8. Mathematics, Biology and Metabiology -- References -- Chapter 7 Uncertainty in Physics and Computation -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- References -- Chapter 8 Indeterminism and Randomness Through Physics -- Acknowledgments.

References -- Chapter 9 The Martin-Löf-Chaitin Thesis: The Identification by Recursion Theory of the Mathematical Notion of Random Sequence -- WHAT DREW ME TO THE STUDY OF RANDOMNESS -- WHAT WE HAVE LEARNED -- 9.1. The Notion of Martin-Löf-Chaitin Random Sequence -- WHAT WE ARE FIGURING OUT: COMPARISON OF CHURCH-TURING'S THESIS AND MARTIN-LÖF-CHAITIN'S THESIS -- 9.2. Conclusion -- References -- Chapter 10 The Road to Intrinsic Randomness -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- PART III Algorithmic Inference and Artificial Intelligence -- Chapter 11 Algorithmic Probability - Its Discovery-Its Properties and Application to Strong AI -- INTRODUCTION -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- 11.1. Completeness and Incomputability -- 11.2. Subjectivity -- 11.3. Diversity -- 11.4. Computation Costs -- 11.5. Training Sequences -- THE PROSPECTS FOR PROGRESS -- References -- Chapter 12 Algorithmic Randomness as Foundation of Inductive Reasoning and Artificial Intelligence -- INTRODUCTION -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T YET KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- References -- Chapter 13 Randomness, Occam's Razor, AI, Creativity and Digital Physics -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- 13.1. Constant Resource Bounds for Optimal Decision Makers -- 13.2. Digital Physics -- 13.3. Coding Theorems -- 13.4. Art and Science -- THE PROSPECTS FOR PROGRESS -- References -- PART IV Randomness, Information and Computability.

Chapter 14 Randomness Everywhere: My Path to Algorithmic Information Theory -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS IN THE FIELD -- THE PROSPECTS FOR PROGRESS -- Chapter 15 The Impact of Algorithmic Information Theory on Our Current Views on Complexity, Randomness, Information and Prediction -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS AND THE PROSPECTS FOR PROGRESS -- Chapter 16 Randomness, Computability and Information -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T (YET) KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- Chapter 17 Studying Randomness Through Computation -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- 17.1. The Randomness Aspect of a Set -- 17.2. The Computational Complexity Aspect of a Set -- 17.3. Using Computability to Understand Randomness -- 17.4. Using Randomness to Understand Computability -- WHAT WE DON'T (YET) KNOW -- 17.5. Are We Studying the Right Randomness Notions? -- 17.6. Do the Randomness Notions Really Form a Hierarchy? -- 17.7. Are We Studying the Right Lowness Properties? -- 17.8. So, Again, are our Notions Intrinsic, or Accidental? -- THE MOST IMPORTANT OPEN PROBLEMS IN THE FIELD -- 17.9. Covering a K-trivial by an Incomplete Random -- 17.10. Kolmogorov-Loveland Randomness -- THE PROSPECTS FOR PROGRESS -- Acknowledgments -- References -- Chapter 18 Computability, Algorithmic Randomness and Complexity -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- 18.1. The Downey-Hirschfeldt Monograph -- WHAT WE LEFT OUT, AND WOULD HAVE LIKED TO INCLUDE.

THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- Chapter 19 Is Randomness Native to Computer Science? Ten Years After -- WHAT DREW US TO STUDY ALGORITHMIC RANDOMNESS -- 19.1. Paradoxes Around Algorithmic Information Theory -- 19.2. Formalization of Discrete/Continuous Computability -- WHAT WE HAVE LEARNED? A PERSONAL PICK -- 19.3. From Randomness to Complexity -- 19.4. Formalization of Randomness: Infinite Strings -- 19.5. Random versus Lawless -- 19.6. Randomness and Finite Strings: Incompressibility -- 19.7. Representation and Kolmogorov Complexity -- 19.8. Prefix-freeness -- 19.9. Approximating Randomness and Kolmogorov Complexity -- 19.10. Randomness, Kolmogorov Complexity and Computer Science -- 19.11. Kolmogorov Complexities and Programming Styles -- 19.12. Computability versus Information -- 19.13. Kolmogorov Complexity and Information Theories -- WHAT ARE THE PROSPECTS FOR PROGRESS? -- References -- PART V Computational Complexity, Randomized Algorithms and Applications -- Chapter 20 Randomness as Circuit Complexity (and the Connection to Pseudorandomness) -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T YET KNOW -- THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- References -- Chapter 21 Randomness: A Tool for Constructing and Analyzing Computer Programs -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- WHAT WE DON'T YET KNOW AND THE MOST IMPORTANT OPEN PROBLEMS -- THE PROSPECTS FOR PROGRESS -- Chapter 22 Connecting Randomness to Computation -- WHAT DREW ME TO THE STUDY OF COMPUTATION AND RANDOMNESS -- WHAT WE HAVE LEARNED -- 22.1. Average-case Analysis of Algorithms -- 22.2. Low Probability Events -- 22.3. What Have We Learned: Information Distance -- THE MOST IMPORTANT OPEN PROBLEMS AND THE PROSPECTS FOR PROGRESS.

References.