Chapter 11

RANDOMNESS EVERYWHERE

McGill University’s main campus is located in downtown Montreal, at the foot of the Mont Royal hill, the city’s principal landmark. Just beyond the semicircular stone-and-iron entrance gate and on the right sits Burnside Hall, a box-shaped concrete building housing the mathematics and statistics department.

At two o’clock on a sunny afternoon in mid-April 1998, Burnside Hall’s main auditorium was almost packed, even though the lecture was not scheduled to start until 3:30. The speaker’s reputation had attracted an unusually large crowd for a mathematics talk. Its title, “Randomness at the Heart of Mathematics,” had aroused the interest of local and out-of-town mathematicians and computer scientists, who suspected that Norton Thorp would announce a breakthrough in the generation of random numbers, a subject central to the computer simulation of real-world phenomena.

By the time Andy Stone stepped on stage to introduce a speaker who needed no introduction, every available seat and standing space in the auditorium was occupied. Johanna Davidson was sitting in one of the front rows. She had arrived early, hoping that Andy would introduce her to his famous guest and she could have him sign her copy of Life of a Genius, his recently published biography. But her former teacher was too busy looking after the VIPs invited to the talk, and she obviously was not among them.

Norton Thorp was an artful speaker, and he knew how to structure his lectures in order to maintain the interest of his audience. He would begin with some amusing anecdote or clever story to break the ice and then gradually step up the level of technical difficulty until he reached the climax, some deep new formula or theorem that only a few would understand. But he would then quickly climb down from those conceptual heights to wrap up the talk with some general remarks in plain language about the significance of the new result, often accompanied by philosophical considerations that everybody could appreciate.

As he appeared on stage and approached the lectern, Thorp was received with a sustained round of applause. He thanked the organizers and especially Andrew Stone for the invitation, said a few words about how delighted he was to be in Montreal, a city with “a blend of French and English cultures unique in North America,” and began his talk.

“Computers are supremely fast for doing arithmetic, and they can easily beat humans at the task of, say, adding five hundred numbers. But how about adding infinitely many numbers? Let me tell you a little story.

“Suppose we wished to find the result of alternatively adding and subtracting all the reciprocals of the odd numbers, an infinitely long operation

1/1 − 1/3 + 1/5 − 1/7 + 1/9 − 1/11 + 1/13 − 1/15 + . . .

The numbers appeared on the overhead screen.

“We could use a computer to do the calculations, but one thousand years and zillions of operations later, the machine will still be trying to work out the final answer—although of course, none of us will be around by then.” There were some laughs from the audience. “OK, let’s be fair to the machine and admit that at that point it will have found an answer,” Thorp resumed, “but only a partial and approximate one.”

“In 1671, centuries before the first computers were built, the Scottish mathematician James Gregory proved that the answer to the infinite operation is exactly π/4, establishing at the same time a beautiful and intriguing connection between elementary arithmetic—whole numbers, addition, subtraction—and elementary geometry—the ratio of the circumference of a circle to its diameter. The moral of the story? A machine can add billions of numbers, but it takes a human brain to calculate an infinite sum.”

He struck a key on his laptop and “Randomness at the Heart of Mathematics” flashed on the screen. The talk had changed gears.

“The theory of probability is the best tool humans have devised to deal with random phenomena, that is, those situations involving chance. The simplest example of a random event is the result of flipping a ‘balanced’ or ‘fair’ coin, which can land either ‘heads’ or ‘tails.’ If we repeatedly toss the coin and record each successive outcome by writing 1 (for heads) and 0 (for tails) we’ll end up with a sequence of 0s and 1s, such as, for example, 0001101101. All sequences obtained in this way qualify as ‘random sequences.’ This means that chance alone decides the composition of the sequence—and not, say, some predetermined rule.”

After this elementary introduction he recalled the various attempts made by mathematicians to specify what a random sequence of 0s and 1s precisely is, and he reviewed the most efficient algorithms used to generate pseudo-random sequences on a computer. “A true random sequence is totally unpredictable,” he went on, “it doesn’t obey any law; it is not just that we are not smart enough to figure out the rule or pattern; there is no rule, and in this sense true randomness is indistinguishable from absolute chaos. It is precisely because of this complete absence of any order or structure that a true random sequence cannot be described other than by writing down the entire sequence.

“But how pervasive is randomness? To answer this question, we first need to make a detour through the theory of computation.” The pleasant-looking face of a young man deep in thought appeared on the screen.

“In the summer of 1935, a young Cambridge graduate reflecting on a question in the foundations of mathematics came up with the notion of an ideal computer that could mimic the operations of any computing device. The young graduate was Alan Turing—the brilliant British mathematician behind the cracking of the German Enigma code during the war and considered the father of the modern computer. His ideal computing machine became known as a Turing machine.

“Since Turing’s ideal machine is at least as powerful as any real one, anything a Turing machine cannot do, no real computer—present or future—will be able to do either. As Turing showed, one of the problems his ideal computer cannot solve concerns the automatic checking of computer software. This is the question of determining in advance whether any given computer program, when executed, will eventually terminate its calculation and halt or is destined to run forever—the so-called halting problem.

“Many years later, starting in the 1970s, Gregory Chaitin, a mathematician working at IBM, took a fresh interest in the halting problem. He considered all the programs that could be run on a Turing machine and asked the following question: What is the probability that one of these programs chosen at random will halt? He found that the answer is a number, which he called Omega, whose digits form a true random sequence, in the sense that they have no pattern or structure whatsoever. Chaitin described Omega as a string of 0s and 1s in which each digit is as unrelated to its predecessors as one coin toss is from the next. He presented Omega as the outstanding example of something in mathematics that is uncomputable, and therefore unknowable.

“But Chaitin did not stop there. He began to search for other places in mathematics where randomness might crop up, and he found that it does in its most elementary branch: arithmetic. But if there was randomness at the most basic mathematical level, his hunch was that it must be everywhere, that randomness is the true foundation of mathematics. In Chaitin’s own words: ‘God not only plays dice in physics but also in pure mathematics. Mathematical truth is sometimes nothing more than a perfect coin toss.’

“Was Chaitin right? For many years, the question remained open, but some recent work by two mathematicians at the University of Berkeley appeared to reinforce the idea that randomness—i.e., unpredictability—is as pervasive in pure mathematics as it is in theoretical physics.”

He paused and faced the audience. Every pair of eyes in the room was fixed on the speaker. The silence was so complete that one could hear the noise from the overhead projector’s cooling fan. Ten long seconds went by before Thorp spoke again in a solemn tone fitting the occasion.

“I’ve now found an irrefutable proof that, as Chaitin suspected, randomness is at the heart of mathematics,” he announced, “and the implications of this fact are far-reaching. It means that we may be able to prove some theorems, answer some questions, but the vast majority of mathematical problems are essentially unsolvable. It means, as one of my colleagues has put it, that a few bits of math may follow from each other, but for most mathematical situations those connections won’t exist because mathematics is full of accidental, reasonless truths. And if you can’t make connections, you cannot solve or prove things. Solvable problems are like a small island in a vast sea of undecidable propositions.”

As he pronounced these last words, the aerial view of an island with “Solvable Problems” written on it appeared on the screen. Slowly, the camera began to move away, revealing more and more water around the island, until the water, with the inscription “Unsolvable Problems” floating in it, completely filled the screen and the island all but disappeared.

For the next thirty minutes, Thorp presented the broad lines of his proof: screen after screen of formulas and equations, a pyrotechnics of high-level mathematics accompanied by the speaker’s comments and explanations. It was a brilliant display of the power of the human intellect dealing with abstractions it had itself created in its quest for understanding.

“The complete proof will appear in the Annals of Mathematics and Computing,” he announced almost apologetically, as if acknowledging the fact that very few in the audience could have understood all the intricacies of the demonstration from his necessarily sketchy presentation. He then added a few remarks about the consequences of his discovery for other sciences, in particular physics, so dependent on mathematics for the formulation of its theories, and concluded on a philosophical note.

“Our old friend Pythagoras thought he had discovered the key to the mysteries of the universe: the world was ruled by numbers in an orderly and immutable way. ‘All is number,’ he taught, and so by unlocking the secrets of numbers one could understand anything. He may turn in his grave if he learned that the secrets of numbers are for the most part impenetrable and the fabric of reality is made up of chaos and unpredictability.”

A few moments of complete silence followed, as if the audience were paying its respects to the optimistic conception that most—if not all—mathematical problems could be solved, and then it exploded into a standing ovation.

When the applause subsided, Andy Stone thanked the speaker for “sharing your landmark discovery with us,” and then announced: “Professor Thorp would be happy to take a few questions from the audience.”

Johanna stayed in Montreal overnight, at the house of one her friends from her student days, now a full-time mother of three.

During the long drive back to Boston the next morning, Thorp’s closing remarks about Pythagoras came to her mind, and only then did she become aware of the coincidence: Jule’s “special assignment” also concerned Pythagoras.