Algorithmic Information Theory

Cambridge Tracts in Theoretical Computer Science

by Gregory Chaitin

Chaitin, the inventor of algorithmic information theory, presents in this book 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 the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation.

Genres: Computer Science, Mathematics, Philosophy, Technology

Hardcover

First published October 15, 1987

About the author

Gregory Chaitin is widely known for his work on metamathematics and for his discovery of the celebrated Omega number, which proved the fundamental unknowability of math. He is the author of many books on mathematics, including Meta Math! The Quest for Omega. Proving Darwin is his first book on biology. Chaitin was for many years at the IBM Watson Research Center in New York. The research described in this book was carried out at the Federal University of Rio de Janeiro in Brazil, where Chaitin is now a professor. An Argentine-American, he is an honorary professor at the University of Buenos Aires and has an honorary doctorate from the National University of Cordoba, the oldest university in Argentina.

Reviews

[Nick Black]

Hahha, I was telling someone the other day, "the thing about Chaitin is that every book I've read by him points out, not once but several times, that he thinks himself the third in a line going back through Turing to Gödel. This makes him not only the greatest living computer scientist, but the greatest computer scientist of all time, Turing being a mathematician and Gödel a logician. They (his books) can get very messianic at times, but without the humility we've associated since Golgotha with a Deliverer -- think of a very unhappy universe where Michio Kaku had written more than autohagiographic pop science balderdash and a forgettable quantum chromodynamics textbook. He'd want fucking statues set up, and seven comely maidens of virtue true each nine years." And what would be the one-line Amazon intro:

More than half a century has passed since the famous papers GÖDEL (1931) and TURING (1937) that shed so much light on the foundations of

I'd put a dollar on a self-mention within forty words from there.

[Nick Black]

Free PDF (Thanks, Dr. Chaitin!), 2009-05-01. What better way to celebrate May Day than with this classic ball-buster? My Livejournal's long closed, but I've been thinking of starting a purely technical blog; this book shows up in tonight's inaugural post.

[Michael · Rating 4 out of 5]

http://blog.fogus.me/2008/12/19/bookp...

-m