Volume I in
Cambridge Tracts in Theoretical Computer Science
October 1987 | Hardback | 192 pages | ISBN: 0521343062 December 2004 | Paperback | 190 pages | ISBN: 0521616042 Cambridge University Press Order from the publisher or Amazon, Barnes & Noble. |

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.

An exponential diophantine equation is explicitly constructed with the property that certain assertions are independent mathematical facts, that is, irreducible mathematical information that cannot be compressed into any finite set of axioms.

This is the first book on this subject and will be of interest to computer scientists, mathematicians, physicists and philosophers interested in the nature of randomness and in the limitations of the axiomatic method.

``Gregory Chaitin... has proved the ultimate in
undecidability theorems..., that the logical structure of
arithmetic can be random...
The assumption that the formal structure of arithmetic is precise and
regular turns out to have been a time-bomb, and Chaitin has just
pushed the detonator.''
*Ian Stewart in Nature*

``No one, but no one, is exploring to greater depths the amazing
insights and theorems that flow from Gödel's work on undecidability
than Gregory Chaitin.
His exciting discoveries and speculations invade such areas as logic,
induction, simplicity, the philosophy of mathematics and science,
randomness, proof theory, chaos, information theory, computer
complexity, diophantine analysis, and even the origin and evolution of
life.
If you haven't yet encountered his brilliant, clear, creative,
wide-ranging mind, this is the book to read and absorb.''
*Martin Gardner*

``...a dazzling *tour de force.*'' *American Scientist*

``If you're interested in computability theory and computational complexity,
*Algorithmic Information Theory* belongs on your bookshelf.'' *AI Expert*

Preface

Chapter 1---Introduction

Part I---Formalisms for Computation: Register Machines, Exponential
Diophantine Equations & Pure LISP

Chapter 2---Register Machines

Chapter 3---A Version of Pure LISP

Chapter 4---The LISP Interpreter EVAL

Part II---Program Size, Halting Probabilities, Randomness & Metamathematics

Chapter 5---Conceptual Development

Chapter 6---Program Size

Chapter 7---Randomness

Chapter 8---Incompleteness

**
Chapter 9---Conclusion
Bibliography
Appendix A. Implementation Notes
Appendix B. The Number of S-Expressions of Size N
**

Erratum: on page 111,
Theorem I0(q), ``*H _{C}*(