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.
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? If it is already finished, why is it taking so long to publish it? Surely it can't take a whole year to setup the press to print the book.
Edward Burr
Having a smoking section in a restaurant is like having a peeing section in a swimming pool.
Comment removed based on user account deletion
It is rarely so technical as to terrify and his sense of humor and careful exposition makes reading his stuff enlightening and fun all at once.
Highly recommended.
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.
Even if the writer's conclusion is true, it is not so obvious as to justify stating it without argument.
Those who would give up essential liberty to purchase a little temporary safety, deserve neither liberty nor safety.
I'm too lazy to look up which mathematician/physicist said this:
"There are only two kinds of math books: those you can't read past the first page, and those you can't read past the first sentence."
Anyway, Chaitin's other books are really interesting too. There is one called "The Limits of Mathematics" which discusses Godel's proof and even "shows" it interactively with some LISP code at the end. The whole book is free online here, which is a great deal for a very interesting Springer text. Some people think Chaitin too arrogant, but there's not denying he's a great mind.
FYI, the continuum hypothesis is neither true nor false (or BOTH true and false, depending on how you think about it :).
It is independent of the rest of set theory... much like Euclid's parallel postulate is to geometry. You can assume it's true, or assume it's false, and you get different versions of set theory in the end. Similar to the existence of both euclidean and non-euclidean geometries.
Many people don't realize that there are multiple versions of something as fundamental to mathematics as set theory! Check out the Axiom of Choice for another example of something that's neither true nor false in set theory.
My favorite proof involving cardinality and set theory is the proof that there are the same number of integers as fractions... so simple that a school kid can understand every step, yet so profound a conclusion!
DiscDividers tabbed plastic CD dividers: divider cards f
We spent about half a semester going from Maxwell's equations to the thin lens approximation.
In a mathematically contiguous manner--no hand waving arguments, all solid derivations and proofs.
With lab.
From electromagnetic theory through to everyday optics. It was fucking beautiful.
Well, I have to go now. I have a date. With my wife.
Nope. Still pegged.
"Reality is that which, when you stop believing in it, it doesn't go away." - Philip K. Dick
Hmmmm ! I don't know about maths or geometry but some of the best kicks I got was from a book called "The Cosmological Argument from Plato to Liebniz" by William Craig Lane. In particular the chapter on Don Scotus' form of the argument was a logical tour de force. Really blew my mind. Of course these arguments are proofs not demonstrations so if you like logical forms with a theological bent check this out its last imprint was 2001.
Well, in the 3rd paragraph of Chapter 1, he sets himself right alongside Goedel and Turing. Off to a great start!
I made a PDF version of the book if anyone's interested.
There are only so many properties of real numbers that we can actually describe in words. (Same number as the cardinality of N.) Most of these properties are either almost always true (i.e. the set of numbers for which it's not true is not dense [wolfram.com] in R) or almost always false. A random number is one that is on the "almost always" side for each of these properties; i.e. transcendental, normal [wolfram.com], non-computable, non-compressible, etc.
Here's a simple demonstration of denumerable numbers at Paul Bourke's page.
"Indenumerable" is typically called "uncountable". The short explanation is that there are two (at least) "sizes" of infinity, countable infinity and uncountable infinity. If a set of numbers is countably infinite, then you could count them all in infinite time. Technically, this means the set can be put into a one-to-one correspondence with the integers. Uncountably infinite sets are infinite and cannot be put into a one-to-one correspondence with the integers. It is somewhat counterintuitive, but an uncountable set has more elements than a countable set, although both are infinite. The real numbers are uncountable.
I thought "omega" was already taken in number theoretical circles--the surreal number consisting of up-up-up-up-... ("up-hat")? Hell, Cantor broke out the Hebrew numbers to express his weird idea. That link uses omega in its own way. This guy really should have tried a little harder.
blarg.
Random technically means non-deterministic. If you want to nitpick, yes numbers generated by an algorithm aren't random, but some algorithms are "cryptographically secure" which means given the previous numbers, one cannot predict the next number w/ certainty or even high probability. There's also the concept of probability distributions which are random in the sense that one cannot for sure know the value but one can know the expected value and the probability of anything being the value.
In sum, random has very different connotations depending on it's use. I have been under the impression that omega in math refers to the first uncountable ordinal number (cite: wikipedia.org) which by definition can have no numeric value associated to it.
The sorts of people who reject the Axiom of Choice (disclaimer: I'm still undecided on the matter) insist on a "constructive" set theory--meaning you can't pull examples of sets that "ought to exist" out of thin air, you have to build them out of the Zermelo-Fraenkel Axioms (minus the Axiom of Choice, of course).
They have a distinction between truth and provability. A statement is true if no counterexample exists (can be constructed), and a statement is provable if there exists a proof of it using the ZF axioms. Using the words "truth" and "provability" in that way, it's clear that the unprovability of the continuum hypothesis is itself proof of its truth. If a counterexample could be constructed (a set with cardinality greater than that of the integers and less than that of the reals), the hypotheis would be provably false. But since it's known to be unprovable, it must be impossible to construct such a set. And the nonexistence of a counterexample is the definition of truth.
It may not actually be inconsistent to use a version of set theory that includes the negation of the continuum hypothesis as an axiom (I'll call it the NCH axiom for Negation-Continuum-Hypothesis), but very few mathematicians (even those who accept the axiom of choice) would accept such a system. Informally, axioms are supposed to be self-evident truths. Even the Axiom of Choice merely extends a statement that is provably true in the finite case to the infinite case, but the NCH axiom asserts, for no self-evident reason, the existence of an exotic set with properties that aren't even trivial to define. The Continuum Hypothesis is technically unprovable, but unless you're actually doing formal mathematics you can safely think of it as true.
The original Howling Frog is a fictional character and has no UID.
Easy. Everyone knows this, but signaling your intent to make a bad joke by leading with the <bad joke> will cause your reader to either skip your post or be forwarned about the joke, and the only thing worse then a bad joke is a bad joke that you know is coming.
The </bad joke> by itself is more of an apology- "yea, I made a bad joke, I know it was bad."
Godel's Incompleteness Theorem does NOT state that no FAS can be complete (any statement that is true under it's notation is provable is true). The first-order propositional calculus & first-order predicate calculus are both complete axiomatic systems (assuming proof of the former, I have done a proof of the latter). It states that any FAS capable of expressing the natural numbers cannot be complete which means no mathematical axiomatic system can yield a complete system. Any system that allow for unrestricted comprehension allows for variants of Russel's paradox - let us have A be the set of all sets that do not contain themselves and only those sets that do not contain themselves. does A contain itself? either answer is contradictory.
The idea that a statement might be "true" independent of a model appeals to some Platonic view of mathematics. When you're talking about the "truth" and "falsehood" of a statement, you need to specify within which model.
Case in point: there are legitimate reasons to reject the full Axiom of Choice if you're working in the area of Descriptive Set Theory, where statements about determinacy matter. The Axiom of Choice rejects useful (and hyper-strong) statements like "every game on a set is determined" (never mind what 'game' and 'determined' mean). In general weaker versions are used in areas like this, such as the Axiom of Dependent Choice.
The way that the Continuum Hypothesis (CH) was shown to be independent (what you call unprovable) from ZFC was showing that there exist models of both ZFC + CH and ZFC + ~CH. It wasn't shown first that CH is unprovable, with the other statements as corollaries.
In general questions about infinities are not going to affect you as a mathematician but you can't just say 'oh the Continuum Hypothesis is true' if you're working near that area. If you are working in an area where the continuum hypothesis matters (logic), you can't be so flippant. If you're working in an area where it doesn't matter, why bother worrying about such technicalities in the first place?
Chaitin's ideas are quite profound both in expanding upon theories of computation:
Goedel -> Turing -> Chaitin
and also in opening up new areas of mathematics and physics, much as chaos theory did.
Understand - the randomness Chaitin is dealing with is NOT the pseudo-random output of a transcendental equation, or of finite state automata (ala Wolfram) - these are truly random numbers that are not being computed, but rather revealed.
Chaitin is also a lisp hacker who (at least in previous books) includes lots and lots of code so you can play with the numbers yourself.
His writing style is a little bit too casual for me (lots of exclamation points), but if you want to learn more about TRUE randomness then go to the source.
Also let me add that Chaitin is a really nice guy - sent him some questions after reading one of his essays several years ago and he answered them straight away.
The reviewer is talking about real numbers. Your intuition about randomness is derived from numbers such as one encounters in a computer or a physical instrument. However, these are not real numbers, they are truncations of real numbers. There are only countably many numbers you can represent on a computer, whereas there are uncountably many real numbers.
There's no such thing as a random number on a computer, because once you single a number out for attention, it isn't random anymore. But, in a technical sense revealed by RTFB, "almost all" real numbers can't be counted. They can't be named exactly, in a way that would allow you to generate them to arbitrary precision. This must be so, because such precise name is a computer program, and there are only countably many computer programs. These numbers are "random" in the sense that it is impossible to single one out for special attention. Although "almost all" real numbers are random, you can't specify a single example!
"The good reader is a rarer swan than the good writer."
Actually, Gödel only proved the incompleteness of Arithmetics.
No - it is more general than that. To quote Nagel and Newman:
"He proved it impossible to establish the internal logical consistency of a very large class of deductive systems.."
Arithmetic was only one example of this.
It is also noteworthy that his contributions aren't solely in the field of mathematics - he has contributed some groundbreaking work in the area of compiler research, such as this paper.
"I love my job, but I hate talking to people like you" (Freddie Mercury)
A word of warning: Chaitin is an entertaining writer, but he is not a careful writer. His purely mathematical theorems and proofs are perfectly fine, of course, but when his thoughts turn philosophical, he is prone to fairly idiosyncratic and dubious thinking.
For example, in one article he inexplicably quotes Einstein to make a point about philosophy of math. In the quote, Einstein alleges that mathematical axioms are invented by humans. Chaitin proudly proclaims that this shows Einstein is an "empiricist". This is a very unusual use of the term "empiricist", not at all consistent with what philosophers of mathematics would mean if they used the term.
Chaitin also defines technical terms (like random) and then pretends he uses them in their usual, non-technical sense. But his definition of random is not the same as its usual sense. For Chaitin, there is a non-zero probability that a random source of 0's and 1's produce a "random" string. This probability goes to 0 as the length of the string goes to infinity, but even then the random source may produce a non-random string (it is a possible event with probability 0).
Finally, Chaitin produces his "random" number Omega, and proudly proclaims that he has proven some mathematical claims are "true for no reason". I don't really know what this would even mean, but unless it means "some equations involve random numbers" then it's not clear how he's proved it.
Anyway, my comments are not referring to this new book, which I have not read, but only to a few articles of Chaitin's that I've read in preparation for a course. For a coherent and clear criticism of Chaitin's work, see Panu Raatikainen's articles.
Phiwum's law: anyone that names an obvious law after himself and then puts it in his own sig is just pathetic.