Gregory J. Chaitin

Picked this off the shelf at Dymocks on Sunday never having heard of this guy. Needless to say, I finished it Monday morning and I am now a Chaitin convert. He is dead right that Godel's theorem is hard to follow told in the normal context and it much much clearer told from an information theoretic perspective. Has opened me up to a new vista of how to think about all these things (probability, randomness, completeness, inference, reconstruction, compression, theory, models, etc. etc...).

"Metabiology": Chaitin, whose version of algorithmic information theory revealed the full extent of the limitations of pre-Gödel and pre-Turing mathematics, in these remarkable 123 pages and in his usual free-wheeling ("creative") way describes a mathematical model for investigating the theoretical effectiveness of Darwinian evolution. In the model, the genomes of organisms take the form of the bit-sequences of certain computer programs, and fitness for survival is represented by the show more computational power (precisely defined) of those programs. Chaitin has proved that the time complexity for the process of producing higher-"fitness" programs is between N^2 and N^3 when the process is one of cumulative random mutations, this being vastly better than that (2^N) for non-cumulative random mutations and almost as good as that (N) for the imaginary limit of "intelligent design". show less

A very clear introduction to the main ideas of algorithmic complexity and how they connect with epistemology. The basic idea is that there are certain facts that cannot be explained in the sense that any explanation is provably more complex than the facts themselves. A very nice feature of this book is Chaitin's enthusiasm for doing mathematics and the sense of elation, adventure and discovery (as opposed to rule following) that goes with it. The idea that insight comes first and proof later show more and that insight is hard hard work that, when reached, brings great great joy. show less

The guru's latest explanation for non-expert readers of his randomness (and algorithmic-information-theory) approach to the incompleteness of mathematics. On computer science, he concludes that "proving correctness of software using formal methods is hopeless" and that software design can't be completed prior to implementation. Edsger Dijkstra may be turning over in his grave.