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

**Information, Entropy and Their Geometric Structures**

by

**Frederic Barbaresco, Ali Mohammad-Djafari**-

**MDPI AG**

The aim of this book is to provide an overview of current work addressing topics of research that explore the geometric structures of information and entropy. This survey will motivate readers to explore the emerging domain of Science of Information.

(

**2152**views)

**Network Coding Theory**

by

**Raymond Yeung, S-Y Li, N Cai**-

**Now Publishers Inc**

A tutorial on the basics of the theory of network coding. It presents network coding for the transmission from a single source node, and deals with the problem under the more general circumstances when there are multiple source nodes.

(

**11029**views)

**Data Compression Explained**

by

**Matt Mahoney**-

**mattmahoney.net**

This book is for the reader who wants to understand how data compression works, or who wants to write data compression software. Prior programming ability and some math skills will be needed. This book is intended to be self contained.

(

**4754**views)

**Entropy and Information Theory**

by

**Robert M. Gray**-

**Springer**

The book covers the theory of probabilistic information measures and application to coding theorems for information sources and noisy channels. This is an up-to-date treatment of traditional information theory emphasizing ergodic theory.

(

**10829**views)