Read This! The MAA Online book review column Meta Math! The Quest for Omega by Gregory Chaitin Reviewed by Marion Cohen

Greg Chaitin is one good mathematician who also seems to be a good human being. I will be saying more about that as this review moves along. His love of math, and of humanity, comes through crystal clear — even more clear than in his previous book of interviews, Conversations with a Mathematician (which I reviewed for the Monthly) — whether he is writing about "his" math, the math of others, or not (ostensibly) about math at all. When he tells us, at the end, that this is really "a book on philosophy, not just a math book", and when, throughout the book, he talks about the philosophy of math, he means "philosophy" in the sense of "philo" — meaning love — love of math, love of humanity, and love of life and existence.

Reading him is everything that I wanted reading Wittgenstein's lectures on math to be! By that I mean, in part, that I relate to Chaitin's questions as a mathematician. They make sense to me, and include many of the things that I always, at various ages and stages, wondered about.

Initially, for faster publication, Chaitin had decided to make the book available for free on the web. Now fortunately, it is scheduled to be published in September 2005 — but will stay on the web.

I am amazed and moved by his humility and sincerity. Perhaps some would say that his plethora of "I's" and "me's" are not humble, but I, and I hope many others, find it endearing when he says, for example, "my omega number", "now let me tell you about...", or "I'd like to begin by sharing with you my vision of mathematics," In fact, the number of "you's" is on the order of the number of "me's", which I believe says something. Another thing I find endearing is his frequent use of exclamation points. (As a writer, I have probably been criticized by editors for this — and also dashes — but frankly, I believe they're okay.)

"I have devoted my life to the attempt to understand what mathematics can and cannot do," he says in his "autobiography" close to the beginning of his book. Of course, this makes us think of Gödel, but Chaitin has a different vision of incompleteness and in general thinks in many new ways about "the limitations of mathematics" (which, perhaps, will turn out to be the very opposite of limitations, in the sense that they lead us to traverse roads and turn corners which we would not have otherwise). "I'll share with you... my doubts and preoccupations," he says in the Preface.

"Yes, I'm a mathematician, but I'm really interested in everything: what is life, what's intelligence, what is consciousness, does the universe contain randomness, are space and time continuous or discrete". In other words, he's really interested in philosophy and physics. (Later on in the book he tells us that he believes that, at least in part, math should be done like physics, namely experimentally.)

"I hope this little book will also convey something of this more personal aspect of mathematical creation, of mathematics as a way of celebrating the universe, as a kind of love-making." This is not the last time in this book that the author makes metaphors like that! Read on, and be patient!

Here are three other notable quotes:

...to understand something is to make it mathematical.

...the computer is even more revolutionary as an IDEA, than it is as a practical device that alters society...

...and what about the so-called real world... Well, I prefer to ignore that insignificant world and concentrate...on the world of ideas...

In the Introduction, besides giving an overview of the book, he continues to try to seduce us into math. "...the view that math provides absolute certainty and is static and perfect while physics is tentative and constantly evolving is a false dichotomy. Math is actually not that different from physics..." (Personally, I don't feel that way, or don't particularly want to feel that way, but I don't have the expertise that Chaitin has.)

"...[mathematicians} are passionate emotional people who deeply care about their art, they are unconventional eccentrics motivated by mysterious forces, not by money nor by a concern for the 'practical applications' of their work. I know, because I'm one of these crazy people myself!... How about you?! Maybe you can do some work in this area... come up with an important new idea... imagine a new kind of question to ask..."

Yes, a new kind of question. Many of the things I work on come from an idea ("alternative arithmetics") that I got when I was a teenager, and Chaitin's Omega also goes 'way back, to when he was fifteen and didn't "get" Gödel's proof. He knew that the reason for this was not any shortcoming of his, but that he thought of incompleteness in a different way. "My Love/Hate Relationship with Gödel's proof" is the title of a section in Chapter Two, "Three Strange Loves: Primes/Gödel/LISP". His youthful questionings were not about Gödel's theorem, but about the proof, "because," he says, "of the lack of balance between the ends and the means, between the theorem and its proof." He felt that the theorem "deserved a deep proof that would give deep insight into the 'why' of incompleteness, instead of a clever proof that only permitted you to have a superficial understanding of what was going on..."

This second chapter, and the third, are the longest in the book. Before getting to Gödel, he can't resist — to our advantage — talking about math in general. The math-in-general that he chooses is the math that either figures directly in his work or inspired it in some way. He gives several proofs (including his own) for the infinity of primes (His own relates to his work, in that it's about "complexity"; if there were a finite number of primes, math wouldn't be complex enough.) "...the best way to learn a new idea is to see its history, ...why someone was forced to go through the painful and wonderful process..."

One passage that intrigues me (and plugs in to questions I have asked, but continues in different directions) is: "Are primes the right concept? ...Perhaps we have been following the wrong clues? How much of our current mathematics is habit, and how much is essential?"

Another is: "...If evolution were rerun, would humans reappear? If the history of math were rerun, would the primes reappear?...[perhaps] mathematics is much more arbitrary than most people think."

I am a little puzzled by what he says about Erdös' idea of "Book proofs", that it's a myth that there's one best proof of every theorem. I don't know that Erdös actually said there was only one "Book proof" — in fact, in Proofs from the Book (a book which was written as a present to Erdös), they actually give six proofs of the infinity of primes (including Euler's, which Chaitin mentions). Probably it's just a question of semantics.

Also, Chaitin says, "If something important is true, there are many reasons that it is true." And although I remember reading in The Interpretation of Dreams that most dreams have many interpretations (and my dreaming experience seems to verify this), I'm not sure that every fact has many reasons. Of course, we'd need to define "reason". (For example, most proofs have more than one step, so many things have to be true in order for the theorem to be true. But as to the underlying reason(s) for something, I'm not sure that they're in the plural.)

Another thought: If something unimportant is true, would the same ruminations apply?

"In a way, math isn't the art of answering mathematical questions, it is the art of asking the right questions, the questions that give you insight, the ones that lead you in interesting directions... that connect with lots of other interesting questions — the ones with the beautiful answers." I wonder. For example, what are wrong questions like? And this seems to contradict what I quoted before, about 'if the history of math were rerun", as well as "[it's] a matter of opinion... fields become popular, and then they become unpopular... Only really important ideas survive..." I do wonder, "What is meant by 'important'? And for how long?"

Still in Chapter Two, he talks about Turing — setting the key concepts in rectangles, such as "Uncomputability implies Incompleteness!" and "My Approach: Randomness implies Incompleteness!" (Yes, exclamation points his.)

Of course, he cannot explain his fantastic ideas fully to non-mathematicians (for whom the book is intended), but he tries, and gets pretty far. "There is a Diophantine equation that is a computer... called a universal Diophantine equation, because it's like a universal Turing machine... and this Diophantine equation means we're in trouble. it means there cannot be a way to decide if [sic] a Diophantine equation has any solutions... Diophantine equations are actually computers! ... What wouldn't I give to be able to explain this to Diophantus and to Hilbert! I'll bet they would understand right away! (This book is how I'd do it) ... and THIS PROVES THAT NUMBER THEORY IS HARD! ... THAT UNCOMPUTABILITY AND INCOMPLETENESS ARE LURKING RIGHT AT THE CORE, IN 2000-YEAR OLD DIOPHANTINE PROBLEMS! LATER I'LL SHOW THAT RANDOMNESS IS ALSO HIDING THERE..." (caps his)

Here's another intriquing passage: "Is it possible that some things really are lawless, random, patternless — even in pure math, even in number theory?... I'll give arguments... that strongly suggest that [that] is the case? In fact, that's the RAISON D'ETRE for this book."

LISP, his third "strange love", isn't a love of my own! Computers still aren't my forte and I didn't understand a lot of that part of the book. "It's a very beautiful language that's highly mathematical in spirit," he says, and it's "a jewel of considerable mathematical beauty, austere intellectual beauty... so you see, this is a real love affair.", but that wasn't (yet) enough for me. I'll have to see and experience it a few more times to feel anything for it. It also wasn't clear to me, what its relation is to the thrust of Chaitin's work. (I'm not saying that it shouldn't be in there; in fact, I like the passages where he puts things in there just because he loves them so much. I certainly do that in my teaching — if it doesn't take up too much time...)

Another passage that interested me: "I'm not really interested in the primes. The fact that they now have applications in cryptography makes me even less interested..." I'd like to know a little more about that, since I have similar sentiments.

Perhaps the title of Chapter Three summarizes that chapter well enough: Digital Information: DNA/Software/Leibniz". It was Leibniz who said, and Chaitin quotes him, "...the sources of invention ... are ... more interesting than the inventions themselves...", and so Chaitin honors him, and gives us a treat, by devoting this chapter to these sources. His take on the Leibniz/ Newton battle pulls no punches. "Newton was a rotten human being." I found it very interesting and refreshing.

Leibniz' discovery of binary arithmetic relates directly to Chaitin's own work, and it's in this part of the chapter that Chaitin goes into his own story of the source of his "invention". "If the experimental data cannot be compressed, if the smallest program for calculating it is just as large as it is (and such a theory can always be found, that can always be done), then the data is lawless, unstructured, patternless, not amenable to scientific study, incomperhensible. In a word, random, irreducible!... and that was the idea that burned in my brain... when I was fifteen years old! ... But working out the details, and showing that mathematics contains such randomness... that's the hard part, that took me the rest of my life... the devil is in the details..."

In this chapter he also talks about biological information — DNA, gigabases, gigabits, and so on. "Certainly biology is the domain of the complex; it's the most obvious example of complexity in the world, not physics, where there are simple unifying principles... simple equations that explain everything..."

His section on "Self-Delimiting Information" includes a fasinating explanation of better and better ways to tell "where one binary message ends and another beings." However, he doesn't actually say what "self-delimiting" means, and I don't get it.

One good thing pedagogically is his policy of ending every chapter with the motivation for and summary of the next (and sometimes the one after that). By the time we're at the end of Chapter Three, our appetites for Chapters IV and V are quite whet.

I tend to think of those two chapters in one clump. They're certainly related. IV is titled "Is the Physical World Continuous or Discrete?" and V is "Mathematical and Philosophical Reasons to Reject Real Numbers". "A number with infinite precision [meaning, roughly, with an infinite non-periodic decimal expansion], a so-called real number, is actually rather unreal!" This idea actually goes back to the famous and ancient Zeno, who asked, "In order to get somewhere we have to first get halfway there, and then halfway there, and so on, so how can anybody get anywhere?" Although we now know that the answer to this "paradox" lies in the fact that each succesive "half-distance" also takes half the time, the questions arising from the "infinitely small" still stand. Chapter V deals with the "unutterable", the uncomputable, and the random. All happen, if we pick a number out of a hat — or, as Chaitin says, from a pinprick — with probability one. He also talks about "Borel's amazing know-it-all real number", which is (perhaps paradoxically) a single real number obtained through taking all the information in the most comprehensive encyclopedia (along, perhaps, with the finite number of brains and psyches of all the sentient beings in this universe); the point is that all the information in the world can be written in the form of a single real number — which causes Chaitin to write, "reals are... problematic from a mathematical point of view, mainly because they contain an infinite amount of information." In this chapter he also makes mention of but doesn't yet define his beloved omega; "even though omega is a real number, you've got to take it seriously!"

"I am very proud of my two incompleteness results in this chapter!" is the very simple and honest beginning to Chapter VI. He then says several intriguing things to get us into the spirit. "Simple axioms with complicated results is where proof helps. But here the axioms have to be as complicated as the result. So what's the point of using reasoning at all... there is no structure or law at all in this particular corner of math." It is around this part in his book that he begins using boxes more frequently, to offset his key ideas, and in one such box appears, in bold letters, "'Axioms equal theorem implies reasoning is useless."

He then takes some time to describe part of the "source" of his ideas, where "source" was elaborated on in Chapter III. He begins by defining the concept of "normal number"; to be brief, a number is normal if and only if, for all integers k, and for all integers b, the base-b expansion has each of the b^k possible blocks of k successive digits with the same limiting frequency (namely, 1/b^k). A real number (again, gotten by playing one-dimensional pin-the-tail-on-the-donkey) is normal with probability 1, but no one has found a specific normal number ("not even π or e", Chaitin wisely adds). The "source" was, in part, "A Conversation on Randomness at City College, NY, 1965", as the section title goes; Richard Stoneham, a colleague of Chaitin's, talked with Chaitin about his determination to find a specific normal number." Chaitin's efforts, as we know, were and have continued to be elsewhere, but that one conversation (the only one between them) had an effect on him. And Chaitin was ecstatic when, decades later, he discovered in a math journal an article by Stoneham in which he showed that "the sum of a natural-looking infinite series was 2-normal" [He didn't exhibit a specific 2-normal number, in the sense of giving a formula for all of the digits, but he found a number in infinite-series form which he could show was 2-normal.]. Chaitin writes, "He and I both found what we were looking for! How delightful!" — one more example of Chaitin's more-than-willingness to further the comraderie among mathematicians.

"I don't think that you can really understand a mathematical result until you find your own proof." I can sincerely commend Chaitin if he truly incorporates this into his own mathematical reading; I confess that I held to it for a very long time but now am quite willing to accept most (though not all) results and use the time, and that result if it's useful, to prove my own theorems.

More important, it is in this next-to-the-last chapter that Chaitin gets to define his Omega. In very brief, Omega is "the halting probability", the probability that a given program (on a fixed already-chosen computer) will halt. Chaitin possibly should have placed more emphasis on the fact that Omega is actually a function of the computer, and not one be-all-and-end-all number, and I also believe that his definition, in one of his "boxes", could be made slightly more clear, so what I am about to write down is a paraphrase of that definition (The bulk of the write-up, of course, was done by Chaitin.):

You run a program chosen by chance (for example, by flipping a coin) on a fixed computer. That is, each time the computer requests the next bit of the program, flip a coin to generate it, using independent choices of a fair coin. The computer must decide by itself when to stop reading the program. This forces the program to be self-delimiting binary info. You sum, over all programs that halt, the probability of getting precisely that program by chance.

So we have a definite equation for Omega:

Omega = the sum, over programs p that halt, of (l/2)^{size of p in bits}
     = the sum, over all non-negative integers k, of (l/2)^k times the number of programs that halt at the kth bit

He concludes this chapter with a section, "Against Egotism". "No scientific idea has only one name on it." This, to my mind, is one of the least original things that Chaitin has to say. Although it probably bears repeating, it's been said already a few times. Also, I detect some possibility for egotism is his next statement, about "the joint production of the best minds." (Emphasis mine.) Also, I for one would be happy to claim one link in an idea. As a writer, I might suggest that Chaitin incorporate this section into the rest of the book, and I might also say that that might not be necessary; Chaitin's commendable humility, along with his reminders of the hierarchy of giants standing on one anothers' shoulders, has already come through big-time.

And now for Chapter VII, the "Conclusion": Recall that it begins with his reminder that this is really "a book on philosophy, not just a math book..." "My intellectual personality is resolutely monotheistic... I am always searching for simple, unifying ideas..." However, he has discovered that "theorem-proving algorithms do not work. One can publish papers about them, but they only prove trivial theorems... the essence of math is in its creativity, in imagining new concepts... not in mindlessly and mechanically griding away deducing all the possible consequences of a fixed set of rules and ideas..."

This lesson comes partly from the computer world. "Similarly, proving correctness of software using formal methods is hopeless. Debugging is done experimentally, by trial and error... you have to design it as you go, not at the very beginning... even though software is pure mind-stuff, not physical, programmers behave like physicists, not mathematicians, when it comes to de-bugging..."

The key words here are "experimentally" and "physicists". As mentioned above, Chaitin believes that mathematics, or a lot of it, needs to be done experimentally (since so much of it is random, and not dependant on any theorems or theory), and in that way at least, math should be approached as physics. "It's too bad," he concludes in this section, "that mathematicians feel that way about experimentation!"

In the section "On Creativity", Chaitin indulges, not himself but his readers, when he does us the favor of telling us, even more, about himself. "I only really feel alive when I'm working on a new idea, when I'm making love to a woman [See, patience paid off! Read the book to find out more!]... or when I'm going up a mountain!... When I'm working on a new idea, I push everything else away. I stop swimming in the morning. I don't pay the bills. I cancel my doctor appointments... I'm not depriving myself of anything. I'm not an ascetic... mornings are very important to me, and I prefer to spend them at home." He also lets on that there is no computer in his home, but there is "art... from so-called 'primitive' cultures like Africa..."

He ends his book with a synopsis of a speculative fiction story by Chad Oliver called "Election Day", about a futuristic society which, every few years, "elects" not a new leader but a new way of life. It is this spirit of extended experimentation that Chaitin would like to see more of, in math and in life.

Of course, I approve of the very end of his book — namely, one of MY poems! (the one which ends, "I am the wanderer / with a lemma in every port.") I also approve of his decision to offer, instead of a bibliography of twenty-or-so pages, a single screen of recent writings connected to his work. I hope to read every one of them.

Publication Data: Meta Math! The Quest for Omega, by Gregory Chaitin. Online publication available at http://www.cs.umaine.edu/~chaitin/omega.html.

Marion Cohen (Mathwoman199436@aol.com) teaches at the University of the Sciences in Philadelphia.

Posted December 3, 2004

Go to... The main Read This! page The index of all reviews The MAA Online front page

Find out... About the Mathematical Association of America Why you should be a member of the MAA How you can help support the activities of the MAA

Read This! is the MAA Online book review column. Contributions are welcome; contact the editor if you'd like to be one of our reviewers. Books for review should be sent to the editor: Fernando Gouvêa, Dept. of Mathematics, Colby College, Waterville, ME 04901. Publishers, please check our reviews information page.