**Algorithmic Information Theory**

by Gregory. J. Chaitin

**Publisher**: Cambridge University Press 2003**ISBN/ASIN**: 0521616042**ISBN-13**: 9780521616041**Number of pages**: 236

**Description**:

The aim of this book is to present 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 Omega, the halting probability of a universal computer if its program is chosen by tossing a coin. The other half of the book is concerned with encoding Omega as an algebraic equation in integers, a so-called exponential diophantine equation. Although the ideas in this book are not easy, this book has tried to present the material in the most concrete and direct fashion possible. It gives many examples, and computer programs for key algorithms. In particular, the theory of program-size in LISP presented in Chapter 5 and Appendix B, which has not appeared elsewhere, is intended as an illustration of the more abstract ideas in the following chapters.

Download or read it online for free here:

**Read online**

(online preview)

## Similar books

**The Limits of Mathematics**

by

**Gregory J. Chaitin**-

**Springer**

The final version of a course on algorithmic information theory and the epistemology of mathematics. The book discusses the nature of mathematics in the light of information theory, and sustains the thesis that mathematics is quasi-empirical.

(

**7241**views)

**Information Theory and Coding**

by

**John Daugman**-

**University of Cambridge**

The aims of this course are to introduce the principles and applications of information theory. The course will study how information is measured in terms of probability and entropy, and the relationships among conditional and joint entropies; etc.

(

**13593**views)

**Theory of Quantum Information**

by

**John Watrous**-

**University of Calgary**

The focus is on the mathematical theory of quantum information. We will begin with basic principles and methods for reasoning about quantum information, and then move on to a discussion of various results concerning quantum information.

(

**6490**views)

**A Mathematical Theory of Communication**

by

**Claude Shannon**

Shannon presents results previously found nowhere else, and today many professors refer to it as the best exposition on the subject of the mathematical limits on communication. It laid the modern foundations for what is now coined Information Theory.

(

**52332**views)