Contents -- Preface -- Technical Contributions -- 1. On Random and Hard-to-Describe Numbers Charles H. Bennett -- 1. Berry's Paradox and the Unprovability of Randomness -- 2. The Search for a "Random" Real Number -- References -- 2. Computing Beyond Classical Logic: SVD Computation in Nonassociative Dickson Algebras Fran¸coise Chaitin-Chatelin -- 2.1. Introduction -- 2.2. Nonassociativity of multiplication -- 2.3. Nonassociative Dickson algebras -- 2.3.1. Presentation of Dickson's doubling process -- 2.3.2. Alternative vectors in Ak, k 4 -- 2.3.3. The splitting Ak = C˜1 Dk, k 2 -- 2.4. SVD computation in Dk and Ak, k 3 -- 2.4.1. c 2 Dk is doubly pure, k 4. -- 2.4.2. Deriving the SVD of a in Ak from that of the tail c in Dk, for k 4 -- 2.4.3. Nonclassical derivation from c to a, k 3 -- 2.5. Is the nonclassical SVD derivation absurd? -- 2.5.1. The conventional analysis -- 2.5.2. Induction and nonclassical singular values -- 2.6. Conclusion -- Acknowledgement -- References -- 3. Janus-Faced Physics: On Hilbert's 6th Problem N. C. A. da Costa and F. A. Doria -- 3.1. Prologue -- 3.2. Hilbert's 6th Problem -- 3.3. A review of axiomatization techniques -- 3.4. Structures, species of structures, models -- 3.5. Axiomatization in mathematics -- 3.6. Suppes predicates for classical field theories in physics -- 3.7. Generalized incompleteness -- 3.8. Higher degrees -- 3.9. The function and the arithmetical hierarchy -- 3.10. First applications: mechanics and chaos theory -- 3.11. Janus-faced physics -- Acknowledgments -- References -- 4. The Implications of a Cosmological Information Bound for Complexity, Quantum Information and the Nature of Physical Law P. C. W. Davies -- 4.1. What are the laws of physics? -- 4.2. Laws as software -- 4.3. The quantum vacuum -- 4.4. Quantum information processing -- 4.5. Unfinished business.

Acknowledgments -- Footnotes -- 5. What Is a Computation? Martin Davis -- The Turing - Post Language -- Codes for Turing - Post Programs -- The Universal Program -- The Halting Problem -- Other Unsolvable Problems -- Undecidable Statements -- Complexity and Randomness -- Unsolvability of Halting Problem -- An Unsolvable Word Problem -- 6. On the Kolmogorov-Chaitin Complexity for Short Sequences Jean-Paul Delahaye and Hector Zenil -- References -- 7. Circuit Universality of Two Dimensional Cellular Automata: A Review A. Gajardo and E. Goles -- 7.1. Introduction -- 7.2. Computing through signals -- 7.2.1. A three states CA by Banks -- 7.3. CA over a hexagonal grid and three states -- 7.4. Life automata -- 7.4.1. Game of life -- 7.4.2. Life without death -- 7.5. Reversible models -- 7.6. Sandpiles -- 7.7. Conclusions -- Acknowledgments -- References -- 8. Chaitin's Graph Coloring Algorithm James Goodman -- References -- 9. A Berry-type Paradox Gabriele Lolli -- References -- 10. in Number Theory Toby Ord and Tien D. Kieu -- 10.1. Recursive Enumerability, Algorithmic Randomness and -- 10.2. Diophantine Equations and Hilbert's Tenth Problem -- 10.3. Expressing Omega Through Diophantine Equations -- References -- 11. The Secret Number. An Exposition of Chaitin's Theory Grzegorz Rozenberg and Arto Salomaa -- 11.1. Introduction -- 11.2. Compressibility of information and randomness. An informal discussion -- 11.3. Prefix-freeness and Kraft's inequality -- 11.4. Computer: a formal notion -- 11.5. Universal computer -- 11.6. Complexity -- 11.7. Fundamental inequalities -- 11.8. Computational and information-theoretic complexity -- 11.9. Self-delimiting programs -- 11.10. Randomness: intuitive considerations -- 11.11. Probability and complexity -- 11.12. Degree of randomness -- 11.13. Magic bits: properties of the secret number.

11.14. Diophantine equations and randomness -- 11.15. Conclusion -- References -- 12. Complexity of the Set of Nonrandom Numbers Frank Stephan -- 12.1. Introduction -- 12.2. Known Results -- 12.3. NRH has r-maximal supersets -- 12.4. The Problems of Friedman and Teutsch -- Acknowledgments: -- References -- 13. Omega and the Time Evolution of the n-Body Problem Karl Svozil -- 13.1. Solutions to the n-body problem -- 13.2. Reduction by ballistic computation -- 13.3. Undecidability and Omega in the n-body problem -- 13.4. Consequences for series solutions -- References -- 14. Binary Lambda Calculus and Combinatory Logic John Tromp -- 14.1. Introduction -- 14.2. Lambda Calculus -- 14.2.1. Some useful lambda terms -- 14.2.2. Binary strings -- 14.2.3. de Bruijn notation -- 14.2.4. Binary Lambda Calculus -- 14.3. Combinatory Logic -- 14.3.1. Binary Combinatory Logic -- 14.3.2. Improved bracket abstraction -- 14.4. Program Size Complexity -- 14.4.1. Functional Complexity -- 14.4.2. Monadic IO -- 14.4.3. An Invariance Theorem -- 14.4.4. Numbers and Strings -- 14.4.5. Prefix codes -- 14.5. Upper bounds on complexity -- 14.6. Future Research -- 14.7. Conclusion -- Acknowledgements -- References -- Philosophy -- 15. Where Do New Ideas Come From? How Do They Emerge? Epistemology as Computation (Information Processing) Gordana Dodig-Crnkovic -- 15.1. Introduction -- 15.2. Epistemology Naturalized by Info-Computation -- 15.3. Natural Computation beyond the Turing Limit -- 15.4. Cognitive Agents Processing Data Information Knowledge -- 15.5. Evolutionary Development of Cognition -- 15.6. Informational Complexity of Cognitive Structures -- 15.7. Conclusions -- 15.8. Acknowledgements -- References -- 16. The Dilemma Destiny/Free-Will F. Walter Meyerstein -- 17. Aliquid Est Sine Ratione: On Some Philosophical Consequences of Chaitin's Quest for Ugo Pagallo.

Introduction -- 17.1. Leibniz's legacy -- 17.2. A German misunderstanding -- 17.3. The darkest of modern thoughts -- 17.4. A Post-modern turning point? -- 17.5. Hyper-modernity and some concluding remarks -- References -- Essays -- 18. Proving and Programming Cristian S. Calude, Elena Calude and Solomon Marcus -- 18.1. Introduction -- 18.2. Proving vs. programming: today -- 18.3. Mathematical examples -- 18.3.1. The twin prime conjecture -- 18.3.2. The Kepler conjecture -- 18.3.3. The Poincaré conjecture -- 18.4. Computer science examples -- 18.4.1. Intel's bug -- 18.4.2. From algorithms to programs -- 18.4.3. Bugs everywhere and Hoare's question -- 18.5. Proving vs. programming: tomorrow -- 18.5.1. Theorems and programs -- 18.5.2. Mathematics = proof? -- 18.5.3. Checking proofs -- 18.5.4. Communication and understanding -- 18.5.5. Rigour: operational vs. conceptual -- 18.5.6. Is it meaningful to speak about the truth of axioms? -- 18.6. Acknowledgements -- References -- 19. God's Number: Where Can We Find the Secret of the Universe? In a Single Number! Marcus Chown -- 19.1. Uncomputability -- 19.2. Undecidability -- 19.3. Compressibility and what scientists do -- 19.4. Randomness -- 20. Omega Numbers Jean-Paul Delahaye -- 20.1. Computable numbers -- 20.2. Omega numbers are much worse -- 20.3. Pure extract of undecidability -- 20.4. Is there a practical definition of omega numbers? -- 20.5. Surely you are joking? -- 20.6. The properties of omega numbers -- References -- Computable and approximable numbers -- Calculating some omega digits -- holds the secret of all mathematical enigmas -- 21. Chaitin and Civilization 2.0 Tor Nørretranders -- 21.1. Chaitin on the beach -- 21.2. Random walk -- 21.3. Worldview -- 21.4. Leibniz -- 21.5. Abstractions? -- 21.6. The Link Age -- 22. Some Modern Perspectives on the Quest for Ultimate Knowledge Stephen Wolfram.

23. An Enquiry Concerning Human (and Computer!) [Mathematical] Understanding Doron Zeilberger -- 23.1. The Arrogance of Science and Mathematics -- 23.2. Skeptics -- 23.3. David Hume's Critique of the Scientific Method -- 23.4. Greg Chaitin and the Limits of Mathematics -- 23.5. How Real Is ? -- 23.6. Do I Believe in ? -- 23.7. Greg Chaitin's Advice About Experimental Mathematics -- 23.8. Stephen Wolfram's Vision -- 23.9. Tweaking Chaitin's and Wolfram's Messages: The Many Shades of Rigor -- 23.10. The Greek Model for Mathematics and Meta- Mathematics -- 23.11. Did Godel Really Prove That There Exist True yet Unprovable Statements? -- 23.12. The Chinese-Indian-Sumerian-Egyptian-Babylonian Model for Doing Mathematics -- 23.13. Formalizing Algorithms: Turing Machines -- 23.14. The Problem with the Chaitin-Kolmogorov Definition of Program-Size Complexity and Randomness -- 23.15. The Ansatz Ansatz -- 23.16. The Polynomial Ansatz -- 23.17. An Ansatz-based Chaitin-Kolmogorov Complexity -- 23.18. It All Depends on the Data Structure -- 23.19. The Strong N0 Property -- 23.20. The Weak N0 Property -- 23.21. Back to Science: The PEL Model -- 23.22. The Probabilistic N0 Property -- 23.23. An Embarrassing Paper of Mine -- 23.24. The Schutzenberger Ansatz -- 23.25. Solving Functional Equations Empirically (Yet Rigorously!) -- 23.26. The Holonomic Ansatz -- 23.27. Functional Equations and Holonomic Functions -- 23.28. In Search of New Ansatzes -- 23.29. Polya's Heuristic Applied to Computer Generated Mathematics -- 23.30. A Very Simple Toy Example -- 23.31. How to Do It the Hard Way -- 23.32. Polya's Ode to Incomplete Induction -- 23.33. The Law of Small Numbers -- 23.34. Inequalities vs. Equalities -- 23.35. The Art of Plausible Reasoning -- 23.36. Don't Get Hung-Up on the N0-Approach -- 23.37. The Wilf-Zeilberger Algorithmic Proof Theory.

23.38. What Is Mathematical Knowledge?.