Randomness and complexity: from Leibniz to Chaitin

Contents......Page 15
Preface......Page 8
Technical Contributions......Page 19
1. Berry’s Paradox and the Unprovability of Randomness......Page 20
2. The Search for a “Random” Real Number......Page 21
References......Page 27
2.1. Introduction......Page 30
2.3.1. Presentation of Dickson’s doubling process......Page 32
2.3.3. The splitting Ak = C1   Dk, k   2......Page 33
2.4.2. Deriving the SVD of a in Ak from that of the tail c in Dk, for k   4......Page 34
2.4.3. Nonclassical derivation from c to a, k   3......Page 35
2.5.1. The conventional analysis......Page 36
2.5.2. Induction and nonclassical singular values......Page 37
2.6. Conclusion......Page 38
References......Page 39
3.1. Prologue......Page 42
3.2. Hilbert’s 6th Problem......Page 44
3.3. A review of axiomatization techniques......Page 45
3.4. Structures, species of structures, models......Page 52
3.5. Axiomatization in mathematics......Page 53
3.6. Suppes predicates for classical field theories in physics......Page 55
3.7. Generalized incompleteness......Page 64
3.8. Higher degrees......Page 70
3.9. The   function and the arithmetical hierarchy......Page 74
3.10. First applications: mechanics and chaos theory......Page 78
3.11. Janus–faced physics......Page 81
References......Page 82
4.1. What are the laws of physics?......Page 86
4.2. Laws as software......Page 89
4.3. The quantum vacuum......Page 95
4.4. Quantum information processing......Page 97
4.5. Unfinished business......Page 100
Footnotes......Page 102
5. What Is a Computation? Martin Davis......Page 106
The Turing – Post Language......Page 108
Codes for Turing – Post Programs......Page 115
The Universal Program......Page 117
The Halting Problem......Page 119
Other Unsolvable Problems......Page 120
Undecidable Statements......Page 123
Complexity and Randomness......Page 125
Unsolvability of Halting Problem......Page 131
An Unsolvable Word Problem......Page 133
6. On the Kolmogorov-Chaitin Complexity for Short Sequences Jean-Paul Delahaye and Hector Zenil......Page 140
References......Page 145
7.1. Introduction......Page 148
7.2. Computing through signals......Page 151
7.2.1. A three states CA by Banks......Page 153
7.3. CA over a hexagonal grid and three states......Page 155
7.4.1. Game of life......Page 157
7.4.2. Life without death......Page 158
7.5. Reversible models......Page 159
7.6. Sandpiles......Page 163
7.7. Conclusions......Page 165
References......Page 167
8. Chaitin’s Graph Coloring Algorithm James Goodman......Page 170
References......Page 171
9. A Berry-type Paradox Gabriele Lolli......Page 172
References......Page 175
10.1. Recursive Enumerability, Algorithmic Randomness and......Page 178
10.2. Diophantine Equations and Hilbert’s Tenth Problem......Page 183
10.3. Expressing Omega Through Diophantine Equations......Page 185
References......Page 190
11.1. Introduction......Page 192
11.2. Compressibility of information and randomness. An informal discussion......Page 195
11.3. Prefix-freeness and Kraft’s inequality......Page 198
11.4. Computer: a formal notion......Page 201
11.5. Universal computer......Page 204
11.6. Complexity......Page 205
11.7. Fundamental inequalities......Page 209
11.8. Computational and information-theoretic complexity......Page 213
11.9. Self-delimiting programs......Page 217
11.10. Randomness: intuitive considerations......Page 219
11.11. Probability and complexity......Page 221
11.12. Degree of randomness......Page 223
11.13. Magic bits: properties of the secret number......Page 225
11.14. Diophantine equations and randomness......Page 229
11.15. Conclusion......Page 230
References......Page 231
12.1. Introduction......Page 234
12.2. Known Results......Page 237
12.3. NRH has r-maximal supersets......Page 239
12.4. The Problems of Friedman and Teutsch......Page 241
References......Page 246
13.1. Solutions to the n–body problem......Page 248
13.2. Reduction by ballistic computation......Page 249
13.3. Undecidability and Omega in the n-body problem......Page 250
13.4. Consequences for series solutions......Page 251
References......Page 252
14.1. Introduction......Page 254
14.2. Lambda Calculus......Page 255
14.2.1. Some useful lambda terms......Page 256
14.2.2. Binary strings......Page 257
14.2.4. Binary Lambda Calculus......Page 258
14.3. Combinatory Logic......Page 261
14.3.1. Binary Combinatory Logic......Page 262
14.3.2. Improved bracket abstraction......Page 263
14.4. Program Size Complexity......Page 265
14.4.1. Functional Complexity......Page 267
14.4.2. Monadic IO......Page 268
14.4.4. Numbers and Strings......Page 269
14.4.5. Prefix codes......Page 270
14.5. Upper bounds on complexity......Page 271
Acknowledgements......Page 275
References......Page 276
Philosophy......Page 278
15.1. Introduction......Page 280
15.3. Natural Computation beyond the Turing Limit......Page 285
15.4. Cognitive Agents Processing Data  Information  Knowledge......Page 287
15.5. Evolutionary Development of Cognition......Page 290
15.6. Informational Complexity of Cognitive Structures......Page 291
15.7. Conclusions......Page 292
References......Page 294
16. The Dilemma Destiny/Free–Will F. Walter Meyerstein......Page 298
17.1. Leibniz’s legacy......Page 304
17.2. A German misunderstanding......Page 307
17.3. The darkest of modern thoughts......Page 309
17.4. A Post-modern turning point?......Page 311
17.5. Hyper-modernity and some concluding remarks......Page 313
References......Page 315
Essays......Page 316
18.1. Introduction......Page 318
18.2. Proving vs. programming: today......Page 319
18.3. Mathematical examples......Page 320
18.3.1. The twin prime conjecture......Page 321
18.3.3. The Poincar´e conjecture......Page 322
18.4.1. Intel’s bug......Page 323
18.4.2. From algorithms to programs......Page 324
18.4.3. Bugs everywhere and Hoare’s question......Page 325
18.5.1. Theorems and programs......Page 326
18.5.2. Mathematics = proof?......Page 327
18.5.3. Checking proofs......Page 328
18.5.4. Communication and understanding......Page 329
18.5.5. Rigour: operational vs. conceptual......Page 330
18.5.6. Is it meaningful to speak about the truth of axioms?......Page 332
References......Page 333
19. God’s Number: Where Can We Find the Secret of the Universe? In a Single Number! Marcus Chown......Page 338
19.1. Uncomputability......Page 341
19.2. Undecidability......Page 348
19.3. Compressibility and what scientists do......Page 353
19.4. Randomness......Page 354
20. Omega Numbers Jean-Paul Delahaye......Page 360
20.1. Computable numbers......Page 361
20.2. Omega numbers are much worse......Page 363
20.4. Is there a practical definition of omega numbers?......Page 364
20.5. Surely you are joking?......Page 367
20.6. The properties of omega numbers......Page 369
References......Page 371
Computable and approximable numbers......Page 372
Calculating some omega digits......Page 373
  holds the secret of all mathematical enigmas......Page 374
21.1. Chaitin on the beach......Page 376
21.3. Worldview......Page 378
21.4. Leibniz......Page 379
21.5. Abstractions?......Page 380
21.6. The Link Age......Page 381
22. Some Modern Perspectives on the Quest for Ultimate Knowledge Stephen Wolfram......Page 384
23.1. The Arrogance of Science and Mathematics......Page 400
23.4. Greg Chaitin and the Limits of Mathematics......Page 401
23.6. Do I Believe in  ?......Page 402
23.9. Tweaking Chaitin’s and Wolfram’s Messages: The Many Shades of Rigor......Page 403
23.11. Did Godel Really Prove That There Exist True yet Unprovable Statements?......Page 404
23.14. The Problem with the Chaitin-Kolmogorov Definition of Program-Size Complexity and Randomness......Page 406
23.15. The Ansatz Ansatz......Page 407
23.16. The Polynomial Ansatz......Page 408
23.18. It All Depends on the Data Structure......Page 409
23.21. Back to Science: The PEL Model......Page 410
23.23. An Embarrassing Paper of Mine......Page 411
23.25. Solving Functional Equations Empirically (Yet Rigorously!)......Page 413
23.26. The Holonomic Ansatz......Page 415
23.30. A Very Simple Toy Example......Page 416
23.31. How to Do It the Hard Way......Page 417
23.32. Polya’s Ode to Incomplete Induction......Page 418
23.33. The Law of Small Numbers......Page 419
23.35. The Art of Plausible Reasoning......Page 420
23.36. Don’t Get Hung-Up on the N0-Approach......Page 421
23.37. The Wilf-Zeilberger Algorithmic Proof Theory......Page 422
23.38. What Is Mathematical Knowledge?; Reliablism......Page 423
23.39. How Necessary is Necessary and How Contingent Is Contingent......Page 424
23.42. Why Is the Computer-Generated Proof of the Four Color Theorem so Beautiful in My Eyes?......Page 425
23.43. Towards an Ansatz Based Mathematics and Meta- Mathematics......Page 426
Reminiscences......Page 428
24. In the Company of Giants Andreea S. Calude......Page 430
25. Gregory Chaitin: Mathematician, Philosopher, and Friend John Casti......Page 434
Œuvre......Page 438
Introduction......Page 440
AIT in a Nutshell......Page 441
Chaitin Research Timeline......Page 442
Challenges for the Future......Page 457
Celebration......Page 460
27. Chaitin Celebration at the NKS2007 Conference......Page 462