THE LIMITS OF MATHEMATICS
By Gregory J. Chaitin
Published by Springer-Verlag
Singapore Pte. Ltd., 1998,
148 pages, $32.00
|
|
THE LIMITS OF MATHEMATICS |
Gödel's incompleteness results shook the very foundations of 20th-century mathematics, just as relativity theory and quantum mechanics redirected 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 that are suggested by the incompleteness results. 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 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 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!
Reviewed by Karl Svozil, University of Technology, Vienna, Austria