Chaitin, the inventor of algorithmic information theory, presents in this book the strongest possible version of Gödel's incompleteness theorem, using an information theoretic approach based on the size of computer programs. One half of the book is concerned with studying the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation.
Author(s): Chaitin, Gregory J.
Series: Cambridge Tracts in Theoretical Computer Science, Volume 1
Edition: Revised edition
Publisher: Cambridge University Press
Year: 2003
Language: English
Pages: 237
Cover......Page 1
Foreword......Page 6
Preface......Page 8
Contents......Page 10
1. Introduction......Page 16
Part I - Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP......Page 22
2.1 Introduction......Page 26
2.2 Pascal's Triangle Mod 2......Page 29
2.3 LISP Register Machines......Page 33
Personae......Page 48
2.5 An Example of Arithmetization......Page 52
tion......Page 62
tion: Expansion of ) 's......Page 66
tion: Left-Hand Side......Page 74
tion: Right-Hand Side......Page 78
3.1 Introduction......Page 82
3.2 De nition of LISP......Page 84
3.3 Examples......Page 92
3.4 LISP in LISP I......Page 96
3.5 LISP in LISP II......Page 97
3.6 LISP in LISP III......Page 101
ns......Page 106
4.2 EVAL in Register Machine Language......Page 109
mary Information......Page 126
of Left-Hand Side......Page 132
Right-Hand Side......Page 134
Part II - Program Size, Halting Probabilities, Randomness, & Metamathematics......Page 138
5.1 Complexity via LISP Expressions......Page 142
5.2 Complexity via Binary Programs......Page 148
nary Programs......Page 149
5.4 Omega in LISP......Page 152
6.1 Introduction......Page 160
6.2 De nitions......Page 161
6.3 Basic Identities......Page 165
6.4 Random Strings......Page 177
7.1 Introduction......Page 182
7.2 Random Reals......Page 187
Bounds on Information Content......Page 200
dom Reals: First Approach......Page 203
dom Reals: j Axioms j......Page 205
dom Reals: H(Axioms)......Page 212
9. Conclusion......Page 216
10. Bibliography......Page 218
Appendix A - Implementation Notes......Page 224
Appendix B - The Number of S-expressions of Size N......Page 226
Appendix C Back Cover......Page 236
