Slashdot Mirror
Metamath! The Quest for Omega
Chaitin's goal is the casual reader's comprehension of an irreducible, uncomputable, and truly random real number. He doesn't actually find one of these numbers, of which there are an indenumerably infinite supply, but he comes as close as a person can to actually referring to it.
Does this sound mysterious (and a little weird)? It is! But this ties in to just the sort of problem mathematicians have been working on for the past hundred or so years. You may be familiar with Goedel's Incompleteness Theorem, in which he proves that no formal axiomatic system (FAS) is powerful enough to prove all of the true statements its notation can express. For a long time, many people were wondering if Fermat's Last Theorem could be one of these statements (although it was finally (and famously) proven by Andrew Wiles about a decade ago). This is the type of "metamathematical" problem Chaitin attacks with his arsenal of complexity and information theory.
Key to understanding the book's premise is understanding the problems involved in defining a truly random number. Chaitin works in binary, so it is easy to find a random number by flipping a coin multiple times, although defining what a random number is supposed to look like (without circularly using the word 'random') is impossible. If you can define exactly what it should look like, then you can use that definition to create (or compress (see below)) a random number. It would not, then, be random.
The next key word is 'reducibility' (or 'compressibility'). If a number is random then it cannot be reduced or compressed into a smaller equation or algorithm. The digits of pi appear to be random, but they are reducible. This entire infinitely long real number can be expressed with just a few symbols- 4*sum_(k=1)^n(((-1)^(k+1))/(2k-1)). The same is true with 'e' or the golden ratio. You might be aware of the distinction between denumerable and nondenumberable infinities-- Chaitin explains this in his book; in short, there are (at least) two kinds of infinite sets, those that map directly to the integers (e.g. the rationals) and those that don't (e.g. the reals). It has been shown that all computer programs may be mapped to integers and hence are denumerable. Any number that can be generated by a computer program (pi, e, etc) therefore is denumerable. For Chaitin's random real number to be truly random, we must look only at real numbers that are indenumerable (cannot be calculated-- otherwise it would be compressible).
Here is where we run into problems-- we can't possibly generate a random real number and we can't even define what it looks like! Chaitin discusses the philosophical arguments for the very existence of such a number, and in the end uses Turing's Halting Program idea to show that a random real number can exist-- and the random real number vaguely referenced in this way, he calls Omega, the halting probability. The probability that an arbitrary program halts is the random real number that Chaitin had been searching for.
But this is not giving away the ending by any means. In fact he tells us this before even embarking upon his journey. What is remarkable about the book is that, in plain English, and using ideas that a non-mathematician like myself can understand, in only 157 pages, Chaitin can explain the grandest ideas on the cutting edge of mathematics. "As you have no doubt noticed," began Chaitin's conclusion, "this is really a book on philosophy, not just a math book. And as Leibniz says... math and philosophy are inseparable."
Although the book can be read quickly and painlessly (there are only a few simple equations in the book), the insights it contains are profound and likely to stick in your brain for some time. Furthermore Chaitin's enthusiastic style is contagious and will leave you on the edge of your seat. He floats through dozens of interesting anecdotes about the great mathematicians-- Leibniz, Newton, Turing, Godel and others--, the process of mathematical discovery from the vantage-point of an actual mathematician, insights into the mind of a working mathematician, and the craft of mathematics, interjecting his own educated thoughts on all of these matters. His style is aimed towards those whose education in mathematics extends only a little past high school and the ideas are simply followed (don't worry if you can't follow my own explanations above; I'm not nearly as skilled an expositer as Chaitin!)
This book is available for free on Chaitin's own website (so why not give it a try?) and also at ArXiv.org. Slashdot welcomes readers' book reviews -- to see your own review here, carefully read the book review guidelines, then visit the submission page.
If this book is reflective of the way I meta-moderate, it should be a breeze!
Hmmm.
Trinity dies while trying to rescue Alan Turing from Zuse's mind control device
Math heart racing? Only on exams
All props to the author and review...but this one isn't going to be an up all night page turner for me.
When the people fear their government, there is tyranny; when the government fears the people, there is liberty.
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
I can honestly answer this question: no
That's a relief, I was starting to think poorly of you.
"The probability that an arbitrary program halts is the random real number that Chaitin had been searching for."
Perhaps the Slashdotting his ~300KB ebook is about to receive would be a good case study...
[Scene: two children on a playground playing cops+robbers]
Chaitin: I got you!
Milhouse: I got you twice!
Chaitin: I got you [thinks very very fast] Omega!
Milhouse: I got you (Omega + 1)!
Chaitin: AAAARGH!!!
Fin
I want to drag this out as long as possible. Bring me my protractor.
Slashdot, what were you thinking?! I was under the impression that only high ranking Starfleet officials were to be told of Omega, yet you go posting a review of it on the front page!
*Publisher not responsible for any mental or physical anguish caused by this book.
I Am My Own Worst Enemy
I've been outnerded.
Man, I thought I was a dork, but I stand humbled in the presence of a math book reviewer. I thought my star trek fanzine and degree in robotics had me prepared, but in one swift book review, all my nerdly accomplishments are like ashes in the wind.
Best Windows Freeware
...Chaitin tell you his own work is the most important work in mathematics? If he does it less than 100 times in the book I may consider reading it.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
He mentions that the book is about defining true random numbers. Now then, this suggests that randomness is a matter of degree, that is, some numbers are more random than others. I suppose the best way to determine the most random number is to poll people to pick a random number and see what the most common choice is.
Unknown host pong.
I'm going as fast as I can, but that movable type is a pain in the ass.
If you can think of a more efficient way to print a book, I'd like to hear it.
I am not a mathematition
Dang. No good in math OR spelling?
--
As a matter of fact, I am a lawyer. But I play an actor on TV.
Don't worry, the people discussing it on Slashdot rarely understand it either.
I have made a beautiful proof that omega > 0.42
but this comment is to small to hold it.
Knud Sørensen
> pick up a non-nerdy book like some good manga or something
/. phrase of the week.
This has to be the
I'll try to explain it in laymans terms for you...
He means that he did not find a number which is part of an infinite quantity of infinite supply and for which there is also an infinite number of. Get it? Good.
Now, for my part I do not give much credibility to a guy who can't even find a number for which there is an infinite quantity. F*ck, just pick one and there you are! But again, I must concede that to find a number (for which similar number exists in an infinite supply) must be harder to do if you look for ONE specific number and you need to look for it thru an indenumerably infinite supply of those. I imagine the complexity of it must be an indenumerably infinite order of magnitude harder to do then to find the bug I am actually tracking which also exist in an indenumerably infinite supply of in the application I am currently working on.
Now I think I've done my fair share of productivity in this world today and I'll just go back to sleep, thank you.
I'd rather be sailing...
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
Slashdot: News for Nerds. Stuff that matters.
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
Yes, so I really should buy a book on how to talk to chicks instead.
If I ever, ever, get tingly over a math book, someone - I don't care who - shoot me.
why, I just don't understand it. Kids these days, what utter slackers. Must be that boogie woogie music you listen to, it eats your branes. Why, back in the day when REAL men learned algebra, we didn't even HAVE grades, we apprenticed, and if you couldn't orally express the factor of the proportionality of the mean square of localised lava flow as a combination of graff-hinderspee spatial nomenclature with the constant moore-livingston entropy tables by the age of three, you were forced to work an extra milking shift in the badger herds!
And we LIKED IT.
The book includes a fascinating account of just how tantalisingly close the Greeks came to inventing calculus. One can only wonder what would've happened if they'd done it.
The Greeks would have sat around having endless philosophical discussions about the ethical significance of the relationship between differentiation and integration. The Romans would have taken it from the Greeks and used it to build things. By now, we'd be speaking Latin in orbit around Alpha Centauri.
The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
I knew a guy who, in grad school, shared an office with a female grad student. Late one night went back to the office to get something, and almost tripped over her while she was, um, pleasuring herself. But that's not the good part. The good part is, as he was backing out of the room, he noticed that in her other hand was a math book, (Cohn's Lie Groups, to be precise). He confessed that, although a math grad student himself, he never found the book quite as exciting as she did.