Algorithmic Information Theory

Large book cover: Algorithmic Information Theory

Algorithmic Information Theory

Publisher: Cambridge University Press
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.

Download or read it online for free here:
Read online
(online preview)

Similar books

Book cover: Around Kolmogorov Complexity: Basic Notions and ResultsAround Kolmogorov Complexity: Basic Notions and Results
by - arXiv.org
Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.
Book cover: Quantum Information TheoryQuantum Information Theory
by - arXiv
A short review of ideas in quantum information theory. Quantum mechanics is presented together with some useful tools for quantum mechanics of open systems. The treatment is pedagogical and suitable for beginning graduates in the field.
Book cover: The Limits of MathematicsThe Limits of Mathematics
by - 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.
Book cover: Logic and InformationLogic and Information
An introductory, comparative account of three mathematical approaches to information: the classical quantitative theory of Claude Shannon, a qualitative theory developed by Fred Dretske, and a qualitative theory introduced by Barwise and Perry.