Thinking about Godel and Turing: Essays on complexity, 1970-2007

Contents......Page 18
Introductory note......Page 0
Section I......Page 24
Section II......Page 25
Section III......Page 26
Section IV......Page 27
Section V......Page 28
Section VI......Page 29
Section VII......Page 30
Section VIII......Page 31
Section IX......Page 32
Section X......Page 33
Section XI......Page 34
References......Page 35
Information-theoretic computational complexity IEEE Transactions on Information Theory, 1974......Page 38
Appendix......Page 46
References......Page 50
Randomness and mathematical proof Scientific American, 1975......Page 52
Algorithmic Definition......Page 53
Model of Inductive Method......Page 55
Minimal Programs and Complexity......Page 57
Properties of Random Numbers......Page 58
Formal Systems......Page 59
Unprovable Statements......Page 61
Limits of Formal Systems......Page 63
Illustrations......Page 64
Further Reading......Page 67
1. Introduction......Page 68
2. Traditional Proofs of Godel\'s Theorem......Page 70
3. Algorithmic Information Theory......Page 74
4. Information-Theoretic Proofs of Godel\'s Theorem......Page 76
5. The Meaning of Godel\'s Theorem......Page 79
6. Directions for Future Research......Page 81
References......Page 82
Randomness in arithmetic Scientific American, 1988......Page 86
Further Reading......Page 94
1. Hilbert on the axiomatic method......Page 96
2. Godel, Turing and Cantor\'s diagonal argument......Page 100
3. The halting probability and algorithmic randomness......Page 105
4. Randomness in arithmetic......Page 111
5. Experimental mathematics......Page 114
Bibliography......Page 119
A century of controversy over the foundations of mathematics Calude & Paun, Finite versus Infinite, 2000......Page 120
The Crisis in Set Theory......Page 121
Bertrand Russell\'s Logical Paradoxes......Page 124
David Hilbert to the Rescue with Formal Axiomatic Theories......Page 125
What is Metamathematics?......Page 128
Kurt Godel Discovers Incompleteness......Page 130
Alan Turing Discovers Uncomputability......Page 132
I Discover Randomness in Pure Mathematics......Page 136
Where Do We Go from Here?!......Page 144
Further Reading......Page 148
A century of controversy over the foundations of mathematics Complexity, 2000......Page 150
Bibliography......Page 172
PART I. THREE INCOMPLETENESS THEOREMS......Page 174
A Beautiful Antique: Godel\'s Proof (1931)......Page 175
What is an Algorithm? [McCarthy (1962), Chaitin (1998, 1999, 2001)]......Page 176
The First Modern Incompleteness Theorem: Turing\'s Halting Problem (1936)......Page 177
Postmodern Metamathematics: The Halting Probability   [Chaitin (1975, 1987, 1998), Delahaye (2002)]......Page 178
What is Algorithmic Information? [Chaitin (1975, 1987, 2001), Calude (2002)]......Page 180
Is Mathematics Quasi-Empirical?......Page 182
Where is Metamathematics Going?......Page 183
What is a Universal Turing Machine (UTM)?......Page 184
Convergence of Theoretical Physics and Theoretical Computer Science......Page 185
To a Theoretical Biology......Page 186
To the Future!......Page 188
Paradoxes of randomness Complexity, 2002......Page 190
References......Page 209
1. Introduction. Why is program size of philosophical interest?......Page 210
2.1. Einstein: Math is empirical......Page 211
2.2. Godel: Math is a priori......Page 213
2.3. AIT: Math is quasi-empirical......Page 216
3. How can we partition the world into distinct entities?......Page 218
References......Page 220
On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility Hogrebe & Bromand, Grenzen und Grenz uberschreitungen, 2004......Page 222
I Plato\'s Timaeus—The Universe is Intelligible. Origins of the Notion of Simplicity: Simplicity as Symmetry [Brisson, Meyerstein 1991]......Page 223
II What Does it Mean for the Universe to Be Intelligible? Leibniz\'s Discussion of Simplicity, Complexity and Lawlessness [Weyl 1932]......Page 225
III What do Working Scientists Think about Simplicity and Complexity?......Page 228
IV A Mathematical Theory of Simplicity, Complexity and Irreducibility: AIT......Page 232
V From Computational Irreducibility to Logical Irreducibility. Examples of Computational Irreducibility: \"Elegant\" Programs......Page 235
VI Irreducible Mathematical Truths. Examples of Logical Irreducibility: Proving a Program is Elegant......Page 236
VII Could We Ever Be Sure that We Had the Ultimate TOE? [Barrow 1995]......Page 238
VIII Should Mathematics Be More Like Physics? Must Mathematical Axioms Be Self- Evident?......Page 239
IX Is the Universe Like   or Like  ? Reason versus Randomness! [Brisson, Meyerstein 1995]......Page 242
Bibliography......Page 244
1. What is algorithmic information theory?......Page 248
2. How Leibniz almost invented algorithmic information theory [7]......Page 249
3. The halting probability   and informationtheoretic incompleteness......Page 253
4. The digital philosophy paradigm shift......Page 256
5. Digital philosophy is Leibnizian; Leibniz\'s legacy......Page 257
6. Acknowledgment; Coda on the continuum and the Kabbalah......Page 258
References......Page 259
Leibniz, randomness & the halting probability Mathematics Today, 2004......Page 262
References......Page 267
Complexity & Leibniz Acad emie Internationale de Philosophie des Sciences, Tenerife, 2005......Page 268
References......Page 271
The limits of reason Scientific American, 2006......Page 272
Complexity and Scientific Laws......Page 273
Sufficient Reason......Page 274
The Number Omega......Page 276
Mathematics and Physics......Page 278
New Mathematical Axioms......Page 279
Experimental Mathematics......Page 280
Box 1. What Is Godel\'s Proof?......Page 281
Box 2. Why Is Turing\'s Halting Problem Unsolvable?......Page 282
Box 3. How Omega Is Defined......Page 283
Box 4. Why Is Omega Incompressible?......Page 284
MORE TO EXPLORE......Page 285
1. Introduction......Page 288
2. Reactions to Cantor\'s Theory of Sets: The Trauma of the Paradoxes of Set Theory......Page 289
2.2. Alternate proof: Any countable/denumerable set of reals has measure zero......Page 290
2.3. Richard\'s paradox: Diagonalize over all nameable reals — a nameable, unnameable real......Page 291
2.5. Borel\'s \"inaccessible numbers:\" Most reals are unnameable, with probability one......Page 292
3. History Repeats Itself: Computability Theory and Its Limitative Meta-Theorems......Page 293
3.2. Alternate proof: Reals are uncomputable with probability one......Page 295
3.3. Turing\'s halting problem: No algorithm settles halting, no formal axiomatic math theory settles halting......Page 296
3.4. Irreducible complexity, perfect randomness, maximal unknowability: The halting probability......Page 297
4. Digital Philosophy and Digital Physics......Page 299
References......Page 301
Introduction......Page 302
Computer Epistemology: What is a mathematical or scienti c theory? How can we judge whether it works or not?......Page 306
Computer Ontology: How real are real numbers? What is the world made of?......Page 311
Conclusion......Page 315
Appendix: Leibniz and the Law......Page 316
References......Page 317
Is incompleteness a serious problem? Lolli & Pagallo, La complessit a di Godel, 2007......Page 320
References......Page 323
Can Darwinian evolution be made into a mathematical theory? Is there a fundamental mathematical theory for biology?......Page 324
A software view of biology: Can we model evolution via evolving software?......Page 326
Pure mathematics has in nite complexity and is therefore like biology......Page 328
Computing   in the limit from below as a model for evolution......Page 330
References......Page 331
1. Introduction......Page 334
3. Using a Real Number as an Oracle for the Halting Problem......Page 335
4. N Cases of the Halting Problem is Only log2N Bits of Information......Page 336
5. The Halting Probability   is the Most Compact Oracle for the Halting Problem......Page 337
7. Storming the Heavens: Attempting to Compute the Uncomputable Bits of......Page 338
References......Page 339
Introduction: What is mathematics?......Page 340
Hilbert: Can mathematics be entombed in a formal axiomatic theory?......Page 341
Godel: \"This statement is unprovable!\"......Page 342
Turing: Most real numbers are uncomputable!......Page 343
Borel: Know-it-all and unnameable reals......Page 345
Theories as software, Understanding as compression, Lawless incompressible facts......Page 346
Provably elegant programs......Page 348
What is the halting probability  ?......Page 349
Concluding discussion......Page 351
Bibliography......Page 352
The halting probability  : Concentrated creativity Obrist, Formulas for the Twenty-First Century, 2007......Page 354
List of publications......Page 356
Acknowledgements......Page 364
About the author......Page 368