The Limits of Mathematics

Institut für Theoretische Physik

University of Technology Vienna Wiedner Hauptstraß e 8-10/136

A-1040 Vienna, Austria e-mail: svozil@tph.tuwien.ac.at

www: 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 T

On 9 Sep 1999, 13:13.