G J Chaitin, IBM Research

Published by Springer-Verlag Singapore, 1999, x + 122 pages, hardcover, ISBN 981-4021-72-5

Order from Springer-Verlag, Amazon, Barnes & Noble

Reviewed in New Scientist, Comp Rev, AMS Notices, J Sci Expl

Translated in Japanese


Having published four books on this subject, why a fifth?! Because there's something new: I compare and contrast Gödel's, Turing's and my work in a very simple and straight-forward manner using LISP.

Up to now I never wanted to examine Gödel's and Turing's work too closely—I wanted to develop my own viewpoint. But there is no longer any danger. So I set out to explain the mathematical essence of three very different ways to exhibit limits to mathematical reasoning: the way Gödel and Turing did it in the 1930s, and my way that I've been working on since the 1960s.

In a nutshell, Gödel discovered incompleteness, Turing discovered uncomputability, and I discovered randomness—that's the amazing fact that some mathematical statements are true for no reason, they're true by accident. There can be no ``theory of everything,'' at least not in mathematics. Maybe in physics!

I didn't want to write a ``journalistic'' book. I wanted to explain the fundamental mathematical ideas understandably. And I think that I've found a way to do it, and that I understand my predecessors' work better than I did before. The essence of this book is words, explaining mathematical ideas, but readers who feel so inclined can follow me all the way to LISP programs that pretty much show Gödel's, Turing's and my proofs working on the computer. And if you want to play with this software, you can download it from my web site.

This book is also a ``prequel'' to my Springer book The Limits of Mathematics. It's an easier introduction to my ideas, and uses the same version of LISP that I use in The Limits of Mathematics. I hope it'll be a stepping stone for those for whom The Limits of Mathematics is too intimidating.

This book began as a lecture on ``A hundred years of controversy regarding the foundations of mathematics'' in which I summarized the work of Cantor, Russell, Hilbert, Gödel, Turing, and my own, and concluded that mathematics is quasi-empirical. I gave several different versions of this lecture in Spanish during two delightful visits to Buenos Aires in 1998 sponsored by the Faculty of Exact Sciences of the University of Buenos Aires. These visits were arranged by Prof. Guillermo Martínez of the Mathematics Department and by Prof. Veronica Becher of the Computer Science Department. To them my heartfelt thanks!

Thanks also to Peter Nevraumont for insisting that this book had to be written. However, the real reason for this book is my conviction that fundamental ideas are simple and can be explained to anyone who is willing to make a little effort. But it has taken me nearly forty years of work to see the simple ideas at the bottom clearly enough that I can present them here in this way!

Final thanks to my management chain at the T.J. Watson Research Center, Paul Horn, Ambuj Goyal, and Mark Wegman, for their encouragement and support.

I dedicate this book to my illustrious predecessors in this quest to understand what are the limits of understanding. And to the one or two children who will stumble upon this book and be inspired to take the next step on this road, as I was inspired many years ago by Nagel and Newman's little book Gödel's Proof. To future understanding!

G.J. Chaitin
11 February 1999

``Il n'y a guère de paradoxe sans utilité.''

— Leibniz


  1. A Hundred Years of Controversy Regarding the Foundations of Mathematics

  2. LISP: A Formalism for Expressing Mathematical Algorithms

  3. Gödel's Proof of his Incompleteness Theorem

  4. Turing's Proof of the Unsolvability of the Halting Problem

  5. My Proof that You Can't Show that a LISP Expression is Elegant

  6. Information & Randomness: A Survey of Algorithmic Information Theory

  7. Mathematics in the Third Millennium?

  8. Bibliography




  1. Page 26, line 9, "it's own size" should read "its own size".