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.
Interesting math books remind me of a book I read a few years ago. Zero: The Biography of a Dangerous Idea by Charles Seife. As fun and interesting as I found math to be, I think that book really did it for me as far as spine tingling mathematics.
Which actually states that any sufficiently powerful formal system can express true propositions which cannot be proven. Typically, "sufficiently powerful" means self-referential to some degree; the system must be able to refer to a propostion within it, and the truth/falsehood of that proposition.
I am not a mathematician, though, so this may not be completely accurate. However, I am fairly sure that it is not difficult to compose a formal system which is provably complete.
I remember your eyes, on the twelfth of July...
now he needs to release it under the new paradigm :)
of academic textbooks.
like the MIT heat transfer book
i kind of like this idea, that if something was
important enough for you to write down for humanity,
you are just doing it for the sake of society.
that would probably take a huge cut out of the
whole "i wrote a book now buy it for my class"
effect...
Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem is one of those other really really exciting mathematics books.
Comment removed based on user account deletion
I was reading a book called "Information and randomness" the other day (highly technical book) and about 50 of the papers in the bibliography are by Chaitin! Seeing how often Chaitin's theorems/discoveries etc. are cited made me realize how vast this guy's contributions are. People so deeply involved in research rarely write popular math books, and so its a pleasant surprise to see that he does, and is quite good at it.
Actually, if this book is compelling, I hope that some of the academic book authors take an example and figure out a way to make math interesting and compelling for children to learn in schools. It is a real shame that most of the public school system in the U.S. makes math seem so boring (the memorization of formulas and crap, rather than learning something that is truly useful and learning how to apply concepts to solve real life problems) that most kids do poorly in math. This, in my opinion, is part of the reason that a lot of the programmers being turned out by schools suck, but think they're hot stuff because they can turn out word processors with VB#.NET or whatever. They really don't have a good solid foundation in math, logic, and science to make really good software. The same problem applies to other areas as well, which is why a lot of U.S. jobs are being outsourced to other countries. I strongly believe that if the public education system here in the U.S. were improved drastically, a lot of employers would see a compelling reason to pay the higher price for domestic workers, because they would get increased value out of their investment.
Anyway, that was a rant, but I think a lot of technical subjects, like math, tie into the greater overall problem of teaching children how to think, how to apply concepts, how to learn something when they don't know the answer, rather than how to memorize the steps to accomplish a particular task, and fail when the task doesn't exactly match, they fail...
An interesting take on these incompleteness theories is Jaakko Hintikka's book "The Principles of Mathematics Revisited." He states, among other things, that Gödel only proved the deductive incompleteness of Arithmetics, but his result is really not that important as it says nothing about the descriptive completeness of systems. His (Hintikka's) point is, that deductive completeness (the possibility to deduce all the possible sentences from given axioms), something that mathematicians had always strived for, isn't really that important; more important is a system's descriptive power.
Man is a slave because freedom is difficult, whereas slavery is easy.
This book is... interesting. Really. Stuffing Franz Kafka, Leibniz and Mahabharata to a math book and ending it with poems, that's a piece of artistic achievement.
Perhaps, should we start some C++ coding in verses?
There you are, staring at me again.
I realize it takes a while to write a book, but doesn't it usually need to be finished before someone can read and review it?
Well, no, actually. It just needs to be mostly finished. Call it a "release candidate."
Surely it can't take a whole year to setup the press to print the book.
There is considerably more to selling a book than printing up a few copies.
Presumably the publisher has other books it's trying to print and sell as well and this one has to "wait its turn."
We're talking marketing here, not manufacturing. Movies sometimes sit "in the can" for years before being released for various reasons. I believe this is common knowledge. The same is true of books.
Or sound recordings. Or automobiles. Or video games. Or whatever.
KFG
The concept that uncountable sets exist is just silly. The sets are simply not well defined. If you can't define something well enough for it to be calculated, then it is not mathematics. Just as I can describe "love" or "happiness", but I cannot give a formal definition of them... they are not math.
These supposed mathematical objects are claimed to exist because someone came up with a formal axiomatic system which assumes they exist. It is a self-fulfilling prophecy.
The problem is that such assumptions result in foundational or metamathematical problems. Formally you can prove the existence of uncountable sets, but semantically all sets are countable. So within the formal system you have one thing, while outside of the formal system you have another... its a sort of semantic inconsistency.
For example, in ZFC set theory you can easily prove that the set of all functions on natural numbers is uncountably infinite. However, the fact that ZFC is a formal system tells us that we can count every function on natural numbers that can be proven to exist in ZFC. This second part cannot be proven within the system, but it is immediate from the fact that finite strings have a one-to-one correspondence with the naturals. So if we assume that ZFC set theory is a formal language for describing the mathematical concept of sets, then we see that an inconsistency exists between the formalism and the mathematical concepts.
Many people, including mathematicians, only think it is necessary to avoid simple inconsistencies... while allowing semantic inconsistencies.
Others, including some of the pioneers of axiomatic set theory, realized that a more constructive foundation was required for mathematics. There are many variations of constructive mathematics. One such branch roughly states that something is mathematical if and only if it can be computed. So mathematical objects are algorithms. This is an interesting formulation of mathematics because all of math is complete, computable, and consistent.
Formal axiomatic mathematics is flawed. In it only guarantees that you have a system for deriving strings in a formal language. It cannot guarantee that these strings have any mathematical meaning. Hence you can derive meaningless things such as a number that cannot be written down or computed to a sufficient decimal expansion.
Omega is not math, its just words. Math invovles precise, absolute concepts. Omega is nothing ore than a formal gesticulation.
i took a course in mathematical philosophy at UPenn about two years ago...having not taken any mathematics courses at all since i had graduated from high school (three years prior), i was surprised to find that 'math' as its commonly known really doesnt make mch of an appreance in readings of this fashion....just be able to keep the shit straight in your head as youre reading and be sure to dissolve any prior notions that you may have regarding the properties of what you know as 'number'...your mind might get blown :-D
I've seen Chaitin present a paper on register allocation. He skilfully held the attention of the entire audience. It wouldn't be surprising if this were a real page turner.
It is not the case that the "continuum hypothesis is known to be true". Nor is it the case that it has been proven to be unprovable, though that is closer to being correct.
The continuum hypothesis is a statement about entities which do not exist in the universe. We know what the statement "2+2 = 4" is about; it's about integers, and since we can count, we're pretty sure that integers exist. The statement "the universe is expanding" is a statement about things we can observe. There can be quibbles about how much of the universe we can see, whether our understanding is really great enough to answer such questions, and so on, but in the end, practically everyone would say that the question has meaning and, therefore, has some kind of answer, even if the answer is no better than "the parts we can observe indeed appear to be expanding".
The continuum hypothesis is different. It is a statement about uncountable sets, which are creations of our mind. If we are right about the laws of physics, there are *no* uncountable sets existing as physical entities in our universe. What this means is that the continuum hypothesis is not a statement relevant to physical reality, and therefore is of quite different character than either "2+2 = 4" or "the universe is expanding". It is a completely reasonable belief system to hold that the continuum hypothesis, being entirely about non-existent mentally generated entities, has no meaning, and is therefore neither true nor false.
To believe that the continuum hypothesis has a definite truth value is a strong philosophical statement. The mathematical philosophy called Platonism holds that mathematical objects, such as uncountably infinite sets, actually exist, and therefore that statements about them such as the continuum hypothesis have meaning, and in fact that such statements are either true or false. Another philosophy of mathematics is formalism, which holds that mathematics is a game we play according to rules. If someone proves a complicated mathematical result about uncountable sets, we admire this as brilliant play of the game, but do we "believe" it? We believe it only if we believe those statements from which the reault was proved. To play and appreciate the game, we don't have to believe in the axioms, and in fact may find it entertaining to play the game starting from axioms we believe to be false. A formalist is unlikely to regard the continuum hypothesis as either true or false.
Another poster said that the continuum hypothesis has been proven to be unprovable. This is an oversimplification. What has been proven is that the continuum hypothesis is unprovable from the standard set theoretic axioms, using standard logic. A formalist admires this statement as itself brilliant game play, but understands that it is meaningful only for this game. Add another axiom, and suddenly you can prove CH. Unless you find the axioms compellingly true, you probably regard a claim of the truth (or falsity) of CH as dubious as a claim that one's goal in life should be to own Park Place. Truth is relative to where you started from.
A good Platonist on the other hand, will generally believe that the contiuum hypothesis is meaningful, and either true or false, if only we were clever enough to figure out which. Since we know we can't prove it from the standard axioms using the standard logic, a Platonist must hope for discovery of a new axiom or a new logic which is intuitively compelling, and which will also allow CH to be proved or disproved. So, to ask "Is CH true?" is assuming a Platonic view of the Universe, and can be answered only by mathematical creativity ("I propose Axiom X, which settles it"), not merely by a clever play of the game of mathematical deduction.
It is my understanding that most mathematicians who care about these issues are in fact Platonists.
There's an even nicer PDF version here, complete with bookmarks and page numbers.