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: Information Theory and Statistical PhysicsInformation Theory and Statistical Physics
by - arXiv
Lecture notes for a graduate course focusing on the relations between Information Theory and Statistical Physics. The course is aimed at EE graduate students in the area of Communications and Information Theory, or graduate students in Physics.
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.
Book cover: Network Coding TheoryNetwork Coding Theory
by - 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.
Book cover: From Classical to Quantum Shannon TheoryFrom Classical to Quantum Shannon Theory
by - arXiv
The aim of this book is to develop 'from the ground up' many of the major developments in quantum Shannon theory. We study quantum mechanics for quantum information theory, we give important unit protocols of teleportation, super-dense coding, etc.