Logo

Algorithmic Information Theory

Large book cover: Algorithmic Information Theory

Algorithmic Information Theory
by

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

Book cover: Quantum Information TheoryQuantum Information Theory
by - ETH Zurich
Processing of information is necessarily a physical process. It is not surprising that physics and the theory of information are inherently connected. Quantum information theory is a research area whose goal is to explore this connection.
(6585 views)
Book cover: Theory of Quantum InformationTheory of Quantum Information
by - 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.
(6055 views)
Book cover: Error-Correction Coding and DecodingError-Correction Coding and Decoding
by - Springer
This book discusses both the theory and practical applications of self-correcting data, commonly known as error-correcting codes. The applications included demonstrate the importance of these codes in a wide range of everyday technologies.
(1027 views)
Book cover: Essential Coding TheoryEssential Coding Theory
by - University at Buffalo
Error-correcting codes are clever ways of representing data so that one can recover the original information even if parts of it are corrupted. The basic idea is to introduce redundancy so that the original information can be recovered ...
(2562 views)