Gregory Chaitin’s Meta Maths is a short book, which meanders pleasantly through various topics: Biological Information (DNA), LISP, several proofs of the infinity of the primes, and the question of whether the universe is discrete or continuous, with accompanying (slightly strange[1]) arguments against the real numbers. Additionally, there’s a good amount of entertaining and idiosyncratic reflection on science, philosophy, and life (“I only really feel alive when I’m working on a new idea, when I’m making love to a woman…. or when I’m going up a mountain!”)
Meta Maths also covers that fascinating tie-in between logic and number theory, Hilbert’s 10th problem: whether or not there’s a procedure which can decide whether any integer-valued equation has integer-valued solutions. Some really ingenious mathematics tells us that this is equivalent to the Halting Problem, which asks whether there’s a procedure which can tell if an arbitrary computer program will halt, or continue to run for ever. The answer in both cases is no.
The meat of the story takes us from Gödel’s Incompleteness, to Turing’s Uncomputability (where the Halting Problem arises), and on to Chaitin’s home turf: Algorithmic Information Theory. Each of these areas subsumes the last, in exhibiting in ever more dramatic style the gaping unknowability at the heart of mathematics. The overwhelming majority of real numbers are completely inaccessible to us (other than through non-constructive existence results, of which Chaitin disapproves, I suppose).
The book is full of diagrams like this:
Axioms → Formal System → Theorems
Program → Computer → Output
DNA → Pregnancy → Organism
Ideas → Mind of God → Universe
In each case the first stage consists of compressed information, the middle stage is where this is unpacked, followed by the final result.
Chaitin’s “dangerous idea” is that almost all information (at least the sort of information which can be encoded in binary), is actually incompressible. That is to say, it cannot be deduced from any axioms simpler than itself. It is a striking thought, and rams home with some force that Gödelian gaps in our mathematics are the rule, not the exceptions. If you pick a real number at random, then with probability 1 you can have no way of writing it out, or naming it under any system you can think of, or indeed referring to it at all without hopeless ambiguity.
The basic definitions of Algorithmic Information Theory are perfectly natural: you define the complexity of a piece of binary information (or anything[2], such as a mathematical theorem, which can be encoded in binary) to be the length of the shortest program which computes it. (In fact the program must be “self-delimiting”, this is the book’s most technical matter.) A real number is defined to be random[3] if the complexity of its first N digits is equal to N (give or take a small error term).
The peg off which the book hangs is the number Ω (“sometimes called Chaitin’s number”, he helpfully adds): the average halting probability for self-delimiting programs.
I may be wrong, but it’s not obvious that you can really do much with Ω (so comparisons with other fundamental constants are surely hyperbole). It’s just a fact, whose interest is that it is a random real, but it is strikingly exceptional, since we can pick it out uniquely (in some sense[4]).
A final word about Chaitin’s punchy prose style! Lots of bold! And exclamation marks!! Loads!!! And more sex than most maths books!
[1] It wasn’t at all clear to me in what he means when he says he’s “against” them, especially as much of the material in the book is rather dependent on their existence.
[2] How long can it be before the “irreducible complexity” berks mangle this stuff?
[3] Be warned, the world abounds with different definitions of randomness.
[4] Of course, Ω is incomputable, and we can only access it via something else we can’t know, namely solutions to the Halting problem. But somehow this seems less unsatisfying when you translate it into the language of Diophantine equations: there is one such Q(n,x1,x2…) which has infinitely many solutions if the nth digit of the binary expansion of Ω is 1, and finitely many solutions if it’s 0.
Richard Elwes - mathematician and writer 
Leave a comment