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.
He doesn't actually find one of these numbers, of which there are an indenumerably infinite supply...
What the heck does that mean?
--
As a matter of fact, I am a lawyer. But I play an actor on TV.
is somebody going to need to understand the book? Unfortunately for myself I was not born with the genius gene, and being in highschool (just finished sophmore year, taking alg3 next year), I don't understand a lot of the more advanced pyshics and math discussed on /.
Man, I thought I was a dork
:)
Well, not to pussyfoot around the issue, you are by virtue of having a Trek fanzine. Any dork can have a Trek fanzine, even one without a degree in robotics, or a brain.
Math is about geekyness, not dorkyness.
But hey, if you weren't such a dork you'd already know that.
KFG
he's described this number in a book with a finite number of numbered pages ..... methinks something's fishy here ....
Of course I haven't RTFB, so maybe this is answered, but I don't believe that randomness is a property of a number, its a property of the method used to generate the number. The reviewer's example of flipping a coin to generate a random binary number is an example of this. I could flip a coin and generate the number 000000 - the method of generation is random, the number itself is clearly reducible and therefore not "random" in the sense described in the review.
I would reserve the term "random" to talk about the generation method, and use more precise terms like "irreducible" for the numbers themselves.
To go further, it may even be that what we mean by a "random" generation scheme is: "a scheme whose generation method I can't predict". This makes randomness a property of a system's knowledge of the generation system. For example, in many situations a computer's psuedo-random number generator is a sufficiently random generation scheme, in some cases (for example cryptography) it is not. psuedo-RNGs are not random (they are deterministic, thus the use of the term "pseudo") but for some uses they effectively are, because the system using the numbers output from them can't (or doesn't need to) predict the next number generated.
So I would propose that "random" refers to the process of generating a number that is in practice non-deterministic in the specific context in which the number is used.
Sailing over the event horizon
Your examples show that you do not actually understand the post you were responding to. Both pi and sqrt(2) are computable numbers. There are a countable number of computable numbers, since each can be specified by a finite computer program.
In fact, one of my favorite examples is Presburger arithmetic, which doubles as a nice example of a problem provably harder than any in NP.
He said they need to be computable. The real numbers you speek of are similar to the "random" numbers the book discusses. If you can define a number - sqrt(2) is a definition - then it can be counted. Take the ascii string that defines a number and convert the bits to one big integer. Now the only uncountable numbers are the ones you can't define in a finite string (or with a finite program) and I challenge you to name one.
Notice also how the reviewer used nested brackets in his review, not once but twice. In my experience, only programmers or mathematicians ever do this with plain english writing.