Welcome to E-Books Directory
This is a freely downloadable e-book.

Algorithmic Information Theory

Algorithmic Information Theory
by Gregory. J. Chaitin

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

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.

Home page url

 Download or read it online here:

Download link

 (0.9MB, PDF)