Welcome to **E-Books Directory**

This is a freely downloadable e-book.

# Algorithmic Information Theory

Read this book online or download it here for free

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