Chaitin, Gregory J., The Unknowable, Springer-Verlag, Singapore, 1999.
Gödel discovered incompleteness, Turing discovered uncomputability and Chaitin discovered algorithmic randomness. The book, which can also be used as an introduction to the author's more technical book [The Limits of Mathematics, Springer, Singapore, 1998; MR 98m:68056], presents these three milestone achievements in a clear, understandable, hands-on way (the reader can play with the basic proof using Chaitin's version of LISP (see http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable)).
Reviewed by Cristian Calude
Chaitin, Gregory J., The Unknowable, Springer Series in Discrete Mathematics and Theoretical Computer Science, 1999.
Here's a close look at the limits of epistemology and logic. Of course, Goethe made many deeper and broader remarks on limitations of Reason (represented by Mephistopheles) in his dramatic work, Faust. The author brings together information theory and computability theory in the context of randomness. For example, some unprovable formal statements (say even in mathematics) are true for no reason; they are true by accident or randomness! Unlike physics (perhaps), there can be no ``theory of everything'' in mathematics or formal logic. The author makes good use of the artificial intelligence programming language, LISP; e.g., a LISP run to illustrate Gödel's proof of his first incompleteness theorem. Among the interesting topics presented are: Gödel's proof of his incompleteness theorem, Turing's proof of the unsolvability of the halting problem, a proof that one cannot show that a LISP expression is elegant, and mathematics in the Third Millennium. The ideas presented here are sufficiently simple that it is suprising to me that Erdös, Gödel or Shannon didn't come up with them earlier!
[A.A. Mullin (Huntsville)]