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: Information-Theoretic IncompletenessInformation-Theoretic Incompleteness
by - World Scientific
In this mathematical autobiography, Gregory Chaitin presents a technical survey of his work and a non-technical discussion of its significance. The technical survey contains many new results, including a detailed discussion of LISP program size.
(5321 views)
Book cover: Lecture Notes on Network Information TheoryLecture Notes on Network Information Theory
by - arXiv
Network information theory deals with the fundamental limits on information flow in networks and optimal coding and protocols. These notes provide a broad coverage of key results, techniques, and open problems in network information theory.
(8775 views)
Book cover: Data Compression ExplainedData Compression Explained
by - 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.
(5163 views)
Book cover: Information, Entropy and Their Geometric StructuresInformation, Entropy and Their Geometric Structures
by - 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.
(2475 views)