NEW SCIENTIST website, 18 December 1999:
books: An accidental man
According to Gregory Chaitin ``some mathematical statements are true for no reason, they're true by accident''. The Unknowable is his extremely readable exposition of the randomness at the heart of arithmetic
NEW SCIENTIST, 18 December 1999, Opinion books, p. 52:
GREGORY CHAITIN wanted to be a physicist. That was before, aged 10 and ``unbearable'', he discovered the Austrian-born logician Kurt Gödel's incompleteness theorem. He suddenly realised that there was something in mathematics just as fundamental and mysterious as quantum theory and relativity.
In 1930, Gödel had proved that most mathematical truths can never be proved. This discovery, combined with the English mathematician Alan Turing's idea that most things can never be computed, dynamited the foundations of mathematics.
Some mathematicians became deeply depressed that absolute certainty had been stripped out of mathematics. Once the dust had settled, however, it became clear that nothing had changed for most mathematicians. Gödel and Turing's results were largely ignored, dismissed as peripheral.
But Chaitin was convinced that Gödel and Turing's theorems about mathematics lay at the heart of maths, and he set out to prove this. In the 1980s, he achieved his goal, showing that Gödel's unprovable truths were random truths. Astonishingly, pure mathematics, the most rigorous of all human endeavours, was built on randomness. ``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,'' says Chaitin.
Chaitin's struggle with these ideas has shed light on the deep connections between probability and the theorems of Gödel and Turing. It led him to develop algorithmic complexity theory, which defines the complexity of numbers in terms of the shortest computer program needed to generate them. An entirely random string of digits is, by definition, its own shortest algorithm—and maximally complex.
Chaitin's measure of the complexity of a number is synonymous with the randomness of its digits (some people find it inadequate for this reason). This led to the discovery of a new number, Ω, which represents the probability that an arbitrary computer program will halt, and which is infinitely more random than π. And it is central to the study of the natural numbers.
So there is randomness at the heart of arithmetic, and therefore of mathematics as a whole. Chaitin's struggle with these ideas has shed light on deep connections between probability and the theorems of Gödel and Turing. He concludes as a result that ``some mathematical statements are true for no reason, they're true by accident''.
The Unknowable is Chaitin's enthusiastic and extremely readable exposition of all these ideas. Here you will meet a man who, far from being depressed by Gödel's result, gets out of bed every morning high on its mind-boggling ramifications. He predicts that the core of the mathematics of the next century will be very, very complex systems—which the search for terse, elegant, short proofs will, perhaps, give way to finding the beauty in formal languages taken as a whole. And—the alarming bit for many—he suggests that the randomness he finds at the heart of mathematics means it will increasingly be explored through experiments on the behaviour of such systems.
One of the most endearing features of the book are the computer programs. They are written in Chaitin's favourite computer language, LISP, to which he helpfully provides a step-by-step guide. Anyone who runs them can demonstrate Gödel and Turing's dramatic results to their own satisfaction. It's a bit like being able to demonstrate quantum uncertainty or relativistic time dilation from your desktop. Amazing.
No wonder Chaitin chose mathematics over physics.
[Astrophysicist Marcus Chown is the cosmology consultant for New Scientist, and author of the books Afterglow of Creation and The Magic Furnace.]