ALGORITHMIC INFORMATION THEORY

G J Chaitin, IBM Research

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

Reviews

``...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

CONTENTS

Foreword by Jacob T. Schwartz
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

ERRATA

G. J. Chaitin, Algorithmic Information Theory, fourth printing, Cambridge University Press, 1992.

Erratum: on page 111, Theorem I0(q), ``HC(s,t)'' should read ``HC(s/t)''.