Randomness and Complexity : From Leibniz to Chaitin.

By: Calude, CristianContributor(s): Chaitin, Gregory JPublisher: Singapore : World Scientific Publishing Co Pte Ltd, 2007Copyright date: ©2007Description: 1 online resource (466 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9789812770837Subject(s): Kolmogorov complexity.;Computational complexity.;Stochastic processesGenre/Form: Electronic books. Additional physical formats: Print version:: Randomness and Complexity : From Leibniz to ChaitinDDC classification: 519.2 LOC classification: QA267.7.R36 2007Online resources: Click to View
Contents:
Intro -- 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´e 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?.
Summary: Key Features:New results in algorithmic randomnessChaitin's own perspective of his scientific resultsEminent contributors including (in alphabetical order) C Bennett, Paul Davies, Martin Davis, Arto Salomaa, Stephen Wolfram.
Holdings
Item type Current library Call number Status Date due Barcode Item holds
Ebrary Ebrary Afghanistan
Available EBKAF00094179
Ebrary Ebrary Algeria
Available
Ebrary Ebrary Cyprus
Available
Ebrary Ebrary Egypt
Available
Ebrary Ebrary Libya
Available
Ebrary Ebrary Morocco
Available
Ebrary Ebrary Nepal
Available EBKNP00094179
Ebrary Ebrary Sudan

Access a wide range of magazines and books using Pressreader and Ebook central.

Enjoy your reading, British Council Sudan.

Available
Ebrary Ebrary Tunisia
Available
Total holds: 0

Intro -- 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´e 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?.

Key Features:New results in algorithmic randomnessChaitin's own perspective of his scientific resultsEminent contributors including (in alphabetical order) C Bennett, Paul Davies, Martin Davis, Arto Salomaa, Stephen Wolfram.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2019. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.

There are no comments on this title.

to post a comment.