Review of The Limits of Mathematicsby Gregory J. Chaitin

K. SvozilInstitut für Theoretische PhysikUniversity of Technology Vienna Wiedner Hauptstraß e 8-10/136A-1040 Vienna, Austria e-mail: svozil@tph.tuwien.ac.atwww: http://tph.tuwien.ac.at/[    \tilde] svozil

http://tph.tuwien.ac.at/[    \tilde] svozil/publ/greg.tex

Gödel's incompleteness results shook the very foundations of 20'th century mathematics, just as relativity theory and quantum mechanics redirected the contemporary physical research. But unlike physics, with a few exceptions contemporary mathematics often appears unimpressed by the incompleteness theorems, which are relegated to formal logics and are mentioned anecdotally. This results in an ignorance of practitioners of the limit of their practice. Consequently, this causes hefty cost overruns due to frantic attempts to solve'' unsolvable questions. For example, while working for the government to oversee a project involving distributed databases, this author experienced the attempt of a contractor to solve'' the halting problem by a program with ever increasing code size. At the time the contractor was confronted with the recursive unsolvability of Turing's halting problem, the chief engineers simply refused to believe the impossibility to complete what they sarcastically called program Hugo'' by then.

Much of Gregory Chaitin's scientific life has been dedicated to the investigation of incompleteness results. He sought the formally strongest and intuitively clearest expression of them. At the same time, he points to new directions which are suggested by the incompleteness results. His book The Limits of Mathematics is a concise and very readable summary of this research. For those of the readership who want a hands-on'' experience of the outlined theory, the book contains a self-contained series of programs to explore the unknowable - at least up to the first knowable bits, after which knowledge gain is very hard.''

Chaitin's primary tool is algorithmic information theory. There, the concept of minimal length of an algorithmic description (program length) of an arbitrary codable object has been introduced consistently for the first time. This measure is then linked to the halting probability of a computer; that is, to the probability that a computer which is confronted with some input, will ever produce a particular output (or any output at all) and halts.

The halting probability is a magic number. It is a measure for arbitrary programs to take a finite number of execution steps and then halt. It contains the solution of all halting problems, and hence of questions codable into halting problems. It contains the solution of the question of whether or not a particular exponential Diophantine equation has infinitely many or a finite number of solutions. And, since the halting probability is provable algorithmically incompressible,'' it is absolutely random in a very precise, formal sense. Therefore, Chaitin's halting probability is both: a mathematician's fair coin,'' and a formalist's nightmare.

I believe that The Limits of Mathematics contains unconventional, new and challenging reading at all levels, laymen and experts alike, the only prerequisite being the willingness to question and if necessary abandon long-held beliefs and prejudices. Enjoy reading the book!

File translated from TEX by TTH, version 1.94.
On 9 Sep 1999, 13:13.