 Algorithmic Information Theory, Third Printing

Presents the strongest possible version of Gödel's incompleteness theorem, using an information theoretic approach based on the size of computer programs.

Publication date: 02 Apr 2003

ISBN-10: 0521343062

ISBN-13: n/a

Paperback: 236 pages

Views: 25,012

Type: Book

Publisher: Cambridge University Press

Post time: 30 Nov 2006 07:57:04

Algorithmic Information Theory, Third Printing Presents the strongest possible version of Gödel's incompleteness theorem, using an information theoretic approach based on the size of computer programs.
Tag(s): Information Theory
Publication date: 02 Apr 2003
ISBN-10: 0521343062
ISBN-13: n/a
Paperback: 236 pages
Views: 25,012
Document Type: Book
Publisher: Cambridge University Press
Post time: 30 Nov 2006 07:57:04
Book Excerpts:

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.

Gödel's original proof of his incompleteness theorem is essentially the assertion that one cannot always prove that a program will fail to halt. This is equivalent to asking whether it ever produces any output. He then converts this into an arithmetical assertion. Over the years this has been improved; it follows from the work on Hilbert's 10th problem that Gödel's theorem is equivalent to the assertion that one cannot always prove that a diophantine equation has no solutions if this is the case.

This book approaches incompleteness by asking whether or not a program produces an infinite amount of output rather than asking whether it produces any; this is equivalent to asking whether or not a diophantine equation has infinitely many solutions instead of asking whether or not it is solvable.

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.

Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem.

He is considered to be one of the founders of what is today known as Kolmogorov (or Kolmogorov-Chaitin) complexity together with Andrei Kolmogorov and Ray Solomonoff. Today, algorithmic information theory is a common subject in any computer science curriculum. Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem.

He is considered to be one of the founders of what is today known as Kolmogorov (or Kolmogorov-Chaitin) complexity together with Andrei Kolmogorov and Ray Solomonoff. Today, algorithmic information theory is a common subject in any computer science curriculum.