DeepRead
Cover of Algorithmic information theory

Algorithmic information theory

Gregory J. Chaitin · 1987

Minds, machines and the future › Information theory and chaos

#8,661 most recommended

About the book

This book covers algorithmic information theory, which measures the information content of a string, or of a mathematical object, by the length of the shortest program that produces it. It is built on program-size complexity, self-delimiting programs, and the theory of computation, and it includes LISP code that implements the central constructions. Chaitin argues that program-size complexity gives a precise, machine-based account of randomness and of information in mathematics. A string is random when no program much shorter than the string itself can generate it. The book's central result is that the halting probability, Omega, is algorithmically random, so any fixed formal system can determine only finitely many of its bits. From this he derives an information-theoretic route to incompleteness, in which a formal system cannot prove that a specific string has complexity above a bound set by the system's own size.

Written by Claude from what it knows of this book.

What Hacker News says 25% recommend · 0% critical

02420092015202020252009 peak · 1
This bookAverage book in Information theory and chaos

In the commenters’ own words

What Open Library readers say

No Open Library reader has rated it yet.

  • 1 want to read
  • 0 reading
  • 0 have read

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

Details

First published
1987
ISBN
9780521616041
Editions known
4 at Open Library
Open Library
OL23034W

AlgorithmsComputational complexityLISP (Computer program language)Machine theory

Explore in the mosaic

Read next: its neighbours on the mosaic