Meta Maths: The Quest For Omega
28th June, 2008
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.
Categories: Maths, Logic | Comments (5) | Permalink
An infinitely bored librarian
23rd June, 2008
Matt, having read my recent articles about set-theory, feeds back:
The best “real world” example of Russell’s paradox I’ve seen (I forget where now) is this: A librarian, bored with work, sets about making two indexes of books in their library. In book one, she lists all books which don’t reference themselves. In book two, she lists all books which do reference themselves. But then she thinks: I’ve just created two new books, so I should list them as well. But neither book references itself, so they should both be listed in book one. But by doing this, book one now does reference itself! So book one should really be listed in book two instead. But if she does this, then book one goes back to not referencing itself!
I like it. Much better than the barber one.
Categories: Maths, Logic | Comments (0) | Permalink
Cantor and Cohen: Infinite Investigators
17th June, 2008
My two humble blog posts have grown into articles at Plus Magazine.
Part 1: the Axiom of Choice
Part 2: the Continuum Hypothesis
Categories: Maths, Logic | Comments (2) | Permalink
Paying too much at the pump? Then support the Windies
4th June, 2008
Plus Magazine has proof positive that if you’re concerned about ever rising oil-prices, you should be cheering for the West Indies.
Categories: Nonsense, Maths | Comments (0) | Permalink
123 Musicophilia
3rd June, 2008
“Absolute pitch is not necessarily of much importance even to musicians – Mozart had it, but Wagner and Schumann lacked it. But for anyone who has it, the loss of absolute pitch may be felt as a severe privation. This sense of loss was clearly brought out by one of my patients. Frank V., a composer who suffered brain damage from the rupture of an aneurysm of the anterior communicating artery.”
The book is Musicophilia by Oliver Sacks.
In it, Dr Sacks writes about many strange and fascinating musical and mental topics. Absolute pitch is one, another is synaesthesia: a mingling of the senses in which musical intervals may have taste, or words and letters have colour. Sacks (a practising neurologist, famous as the author of The Man Who Mistook His Wife for a Hat) describes a host of neurological conditions varying from the commonplace (the annoyingly catchy tune which won’t go away) to the extraordinary: people whose uncontrollable musical hallucinations extend to full symphonies; a man with extremely severe and utterly crippling amnesia (of the sort portrayed in the film Memento) who can nevertheless conduct a choir and sight-read music perfectly; a man with a lifelong uninterest in music, who develops an all-consuming passion for composing after being struck by lightning.
Perhaps the most remarkable chapter is that about Williams Syndrome: a rare genetic condition, resulting in a brain 20% smaller than average, and an IQ typically below 60 (comparable to that of a Down’s syndrome sufferer). People with this condition are usually unable to manage simple single-digit arithmetic. But along with these weaknesses come surprising strengths: they are often communicatively gifted, with extensive vocabularies. Very often they are singularly drawn to music. An example is Gloria Lenhoff, a celebrated singer with Williams syndrome who can perform operatic arias in over 25 languages.
Musicophilia doesn’t offer easy answers to the central questions of music and the mind. Music does seem to be hardwired into our brains at a deep level: musical ability can survive remarkably intact, even in brains ravaged by severe Alzheimer’s. Also suggestive is that each component of music (tempo, pitch, melody, harmony, timbre, rhythm) comes with its own form of amusia, where someone is unable to comprehend (for example) rhythm, but their understanding of melody and harmony is almost unimpaired. Similarly, the link between musical intelligence (the ability to understand music analytically) and its emotional impact is very weak: there are people with excellent ears, but whom music leaves cold; vice versa we all know people who can’t hold a single note, but who adore it.
One message to take away from this book, if you thought that “music therapy” was some sort of pseudo-medical hippy claptrap, is that you are profoundly wrong. It works: for example many Tourette’s sufferers find that drum-circles are a powerful way to overcome their symptoms. But beyond that, often it is the only thing which works: music can provide the sole way to communicate with otherwise unreachable minds.
Categories: Music, Brain Science | Comments (0) | Permalink
Put a little science in your life!
2nd June, 2008
Inspirational stuff from Brian Greene in the New York Times:
Science is a way of life. Science is a perspective. Science is the process that takes us from confusion to understanding in a manner that’s precise, predictive and reliable — a transformation, for those lucky enough to experience it, that is empowering and emotional. To be able to think through and grasp explanations — for everything from why the sky is blue to how life formed on earth — not because they are declared dogma but rather because they reveal patterns confirmed by experiment and observation, is one of the most precious of human experiences.
Categories: General Science | Comments (0) | Permalink