Meta Math!:The Quest for Omega

Gregory Chaitin has done significant work on how computability is limited by complexity. In Meta Math!:The Quest for Omega he gives an account of some of his work aimed at the non-specialist reader. The book starts with his early fascination with Gödel's incompleteness theorem as well as his interest in computing, and in particular the LISP programming language. He explains how several of the philosophical ideas which seem to have arisen with the advent of the computer age, such as the universe being built out of information, were in fact thought of by Leibniz several centuries before.

Chaitin then moves on to consider the real numbers, and in particular the idea of a random real - since the real numbers form an uncountable set, most of them will not have any compact description. In the final number he gets on to the particular random real Ω. and shows what powerful results can be obtained from the idea that a given system has a certain complexity, and this limits the complexity of what can be generated from that system.

The book might seem hard to follow sometimes, but I think it's worth sticking at it, as any problems aren't so much due to technicalities as to the number of new concepts which Chaitin introduces. Indeed his enthusiasm for his work is obvious, and if you read this books then, who knows, maybe you'll pick up some of that enthusiasm too.