This book is a collection of nontechnical lectures by, and interviews of, the mathematician Gregory J. Chaitin. His style in both these settings is extremely clear and personable. What also emerges clearly is the joy he finds in his work, along with positive attitudes towards findings that have been interpreted by some as negative, even disturbing. His attitude is encapsulated in these sentences from the last page of the book: "What if the degree of intelligence needed to begin to understand the universe surpasses our own by as much as our intelligence surpasses that of an ant... ? Well, we have to try to do it anyway."
What first drew me to this book was the clause from its catalog description: "Chaitin discovered mathematical facts that are true for no reason, that are true by accident." It brought me back to my own high-school years, when I asked, "If a thing is true, is that because it could not possibly not be true?" and "If it is possible for there to be an odd perfect number, will there be an odd perfect number?" These were ideas that I was interested in thinking about but not in investigating myself, though, and I soon became involved with other questions. Over the years, I was glad to find out that others were proceeding differently. In particular, I am gratified to see that Chaitin has made, out of what I considered "dirty work", a clean sweep.
Well, as clean as mathematics, or meta-mathematics, can get. "The Limits of Reason" is part of the subtitle of this book, and by that Chaitin means the limits of mathematics as we know it.
How can we rigorously ask the kinds of questions I asked many decades ago, and how can Chaitin rigorously state the meta-fact that there are "mathematical facts that are true for no reason"? The answer has its roots in several ideas---including Gödel's and Turing's---that are extensively discussed in this book. The answer could also be said to lie in a single word: randomness.
How can a single statement be random? It can't. Either it's true or it isn't. What Chaitin has done is to find a "statement-schema" (that is, a set of arithmetical statements Pn indexed by the positive integers) such that the truth of each Pn is equivalent to the truth of a probabilistic statement Qn. In other words, he shows that mathematics can be not only undecidable or incomplete (à la Gödel), but downright random.
So, what are these statements Pn? Well, they're long! They involve a sequence of algebraic equations, each in 17,000 variables, in which the variables appear as exponents as well as bases. Each equation is approximately two hundred pages long. The statement Pn is simply that the nth equation has an infinite number of integer solutions. The probabilistic statements, on the other hand, come from the theory of computability. One considers a single specific number Ω in [0, 1], which (roughly speaking) is the probability that a certain universal Turing machine will eventually halt when it is fed a program encoded in a sequence of binary digits that is produced by a sequence of coin tosses. The statement Qn is then that the nth digit in the binary decimal for Ω is 1. Chaitin explains the "randomness" of Qn in some detail. The basic idea is stated on page 136: "All of my work is based on computers. I use the computer to define what is meant by randomness... I say the data is random if there exists no theory for it, no description more concise than the data itself." In this sense the binary digits of Ω are truly random, and hence the arithmetical statements Pn are also true or false "for no reason."
This is startling, and Chaitin knows it. To our benefit, he hasn't lost sight of his sense of fascination with the strangeness of his results. Throughout the book, he paraphrases his ideas in many well-written and beautiful passages. "I've constructed irreducible mathematical facts... [Y]ou cannot shrink them any more, you cannot squeeze them into axioms... [E]ssentially the only way to prove them is if we directly take each individual assertion that we wish to prove as an axiom" (p. 86). "This is a part of mathematics which is a black hole, where individual questions cannot be answered. You can make statistical statements about the answers. The answers will be one thing or another 50% of the time... It's exactly like tossing a coin... I constructed an area of mathematics where in fact God does play dice, where mathematical truth is accidental... [T]hings are maximally random..." (p. 148).
Chaitin's idea of randomness in pure mathematics has connections with the uncertainty and randomness in quantum mechanics, and that's partly how Chaitin got his ideas. "I took an idea, randomness, from physics and found it in the foundations of mathematics" (p. 145). Throughout the book, as throughout his life, Chaitin has some interesting thoughts about the connection of mathematics with physics. "I think that at the deepest level the implication of Gödel's incompleteness theorem is... that mathematics should be pursued more in the spirit of physics... [N]umber theory has in fact been pursued to a certain extent in the spirit of an experimental science. One could almost imagine a journal of experimental number theory" (p. 80). He later adds that "my first loves were physics and astronomy, and I understand physicists and how they think" (p. 99). Careerwise, Chaitin has had much to gain by identifying with physicists: "Physicists feel much more comfortable with my ideas than mathematicians..." (p. 70).
Incidentally, an interesting discussion of "random" sequences that compares Chaitin's notion of randomness as incompressibility with several others can be found in Volchan [2].
The only bone I would pick with Chaitin is that, at times, he seems to succumb to the myth about mathematics and mathematicians that one has to be obsessed with one's work in order to succeed. "Einstein had a good friend, Michele Besso, with whom he discussed a lot of his ideas... Late in their lives, Besso's wife asked Einstein, why was it that in spite of all his talent, her husband had never managed to achieve anything on his own. `Because he's a good man!' exclaimed Einstein" (p. 110). (Elsewhere in the book Chaitin talks about this same Besso, how he was a "good husband and father" and how that might have stopped him from doing anything important in physics.) In another review [1] I talked at length about this whole phenomenon: why this myth is detrimental to women, and why it's only a myth. I certainly know the obsession of working on a math problem (or even, right now, this "mere" book review), but I believe that it's possible to be obsessed only sometimes, and it might even be possible to regulate one's obsessions. It depends on a lot of factors, and many mathematicians get their ideas mostly when they're not specifically working on mathematics.
So that was my only complaint, but I did have several questions. First, I would love to know whether there are shorter or simpler examples of "random" mathematical statements. And if not, can Chaitin explain why not? [The equation in Pn is essentially the logic design (high-level circuit diagram) for a universal computer expressed as a diophantine equation, and the parameter n is the software for this computer. Wolfram's A New Kind of Science suggests that most simple systems are either trivial or are universal computers, and there is even a section of his book on diophantine equations. If Wolfram is right, then there is probably a very simple diophantine equation that is a universal computer. But the simpler the computer is, the messier and more complicated the programs are. So this simple diophantine equation's parameter n, which is the software, the programs that exhibit randomness, would no doubt be extremely complicated and it would be very hard to see why they work. In generating my equation, I tried to proceed in the most-straightforward manner possible, which minimizes the chance for error. My equation may look big, but it is obtained very simply, as simply as I know how. In my opinion, obtaining a much smaller equation is best viewed as a clever, intricate and messy programming exercise, not as something fundamental. Wolfram thinks quite the opposite; he is looking for the simplest possible universal computers, for the basic building blocks that God used to build the universe.---GJC] Second, I wonder whether the axiom of choice fits into this circle of ideas. [The axiom of choice and the continuum hypothesis are independent of the other axioms of set theory for their own set-theoretical reasons, which have nothing to do with the information-theoretic incompleteness discussed in Conversations. Algorithmic randomness is not the universal source of incompleteness, it is only one among many possible sources for incompleteness.---GJC] Finally, I would like to know more about Chaitin's early childhood. He says that when he was a child he read Gödel's Proof and other important books, and he tells us how he was fifteen when he came up with his main idea. But I also imagine that he might have been doing or thinking interesting mathematical things when he was ten, eight, three, even younger. In general, I'd like to know about the early childhood, perhaps infancy, of all mathematicians. Are the questions they ask different from the questions that nonmathematical kids come up with? (When I was four I sat on the living room floor making paper dolls and chanting "Cut a scissors with a scissors". Was that the mathematician in me or was it a mere young human being?)
I learned a lot of mathematics from reading this book. I gained some insights about Gödel's work and some much-needed feeling for computer science. I had not known about the halting problem, the number Ω, or Lucas's curious (and curiously believable) theorem connecting the parity of binomial coefficients and the binary system. As a "math-poet" I appreciated certain passages that expressed things in ways I had not found before, such as "The best mathematics is inevitable... is fundamental and seems necessary" (p. 61). Finally, I now know the answers to both of my adolescent questions: "Not necessarily."
This book is wonderful in both senses of the word: superlatively good and full of wonder. Nonmathematicians could read it, too, but as I read it, I felt glad (and proud) to be a mathematician!
REFERENCES