Algorithmic Information Theory

by Gregory. J. Chaitin

• ISBN13: 9780521616041
• ISBN10: 0521616042
• Format: Paperback
• Copyright: 2004-12-02
• Publisher: Cambridge University Press

Summary

Chaitin, the inventor of algorithmic information theory, presents in this book the strongest possible version of Godel'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.

Table of Contents

Foreword	vii
Preface	ix
Figures	xi
Introduction	1	(5)
I Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP	6	(85)
The Arithmetization of Register Machines	7	(44)
Introduction	7	(2)
Pascal's Triangle Mod 2	9	(5)
LISP Register Machines	14	(13)
Dictionary of Auxiliary Variables Used in Arithmetization	27	(3)
An Example of Arithmetization	30	(7)
A Complete Example of Arithmetization	37	(3)
A Complete Example of Arithmetization: Expansion of ⇒'s	40	(6)
A Complete Example of Arithmetization: Left-Hand Side	46	(2)
A Complete Example of Arithmetization: Right-Hand Side	48	(3)
A Version of Pure LISP	51	(18)
Introduction	51	(1)
Definition of LISP	52	(7)
Examples	59	(3)
LISP in LISP I	62	(2)
LISP in LISP II	64	(2)
LISP in LISP III	66	(3)
The LISP Interpreter EVAL	69	(22)
Register Machine Pseudo-Instructions	69	(2)
EVAL in Register Machine Language	71	(12)
The Arithmetization of EVAL: Summary Information	83	(4)
The Arithmetization of EVAL: Start of Left-Hand Side	87	(1)
The Arithmetization of EVAL: End of Right-Hand Side	88	(3)
II Program Size, Halting Probabilities, Randomness, & Metamathematics	91	(74)
Conceptual Development	92	(15)
Complexity via LISP Expressions	92	(6)
Complexity via Binary Programs	98	(1)
Complexity via Self-Delimiting Binary Programs	99	(2)
Omega in LISP	101	(6)
Program Size	107	(21)
Introduction	107	(1)
Definitions	108	(4)
Basic Identities	112	(12)
Random Strings	124	(4)
Randomness	128	(18)
Introduction	128	(4)
Random Reals	132	(14)
Incompleteness	146	(17)
Incompleteness Theorems for Lower Bounds on Information Content	146	(3)
Incompleteness Theorems for Random Reals: First Approach	149	(2)
Incompleteness Theorems for Random Reals: | Axioms |	151	(8)
Incompleteness Theorems for Random Reals: H(Axioms)	159	(4)
Conclusion	163	(2)
Implementation Notes	165	(2)
The Number of S-expressions of Size N	167	(9)
Bibliography	176