Douglas Hofstadter - I Am a Strange Loop

The Caspian Gemstones: An Allegory

Leonardo di Pisa’s sequence is brimming with amazing patterns, but unfortunately going into that would throw us far off course. Still, I cannot resist mentioning that 144 jumps out in this list of the first few F numbers because it is a salient perfect square. Aside from 8, which is a cube, and 1, which is a rather degenerate case, no other perfect square, cube, or any other exact power appears in the first few hundred terms of the F sequence.

Several decades ago, people started wondering if the presence of 8 and 144 in the F sequence was due to a reason, or if it was just a “random accident”. Therefore, as computational tools started becoming more and more powerful, they undertook searches. Curiously enough, even with the advent of supercomputers, allowing millions and even billions of F numbers to be churned out, no one ever came across any other perfect powers in Fibonacci’s sequence. The chance of a power turning up very soon in the F sequence was looking slim, but why would a perfect mutual avoidance occur? What do n th powers for arbitrary n have to do with adding up pairs of numbers in Fibonacci’s peculiar recursive fashion? Couldn’t 8 and 144 just be little random glitches? Why couldn’t other little glitches take place?

To cast allegorical light on this, imagine someone chanced one day to fish up a giant diamond, a magnificent ruby, and a tiny pearl at the bottom of the great green Caspian Sea in central Asia, and other seekers of fortune, spurred on by these stunning finds, then started madly dredging the bottom of the world’s largest lake to seek more diamonds, rubies, pearls, emeralds, topazes, etc., but none was found, no matter how much dredging was done. One would naturally wonder if more gems might be hidden down there, but how could one ever know? (Caveat: my allegory is slightly flawed, because we can imagine, at least in principle, a richly financed scientific team someday dredging the lake’s bottom completely, since, though huge, it is finite. For my analogy to be “perfect”, we would have to conceive of the Caspian Sea as infinite. Just stretch your imagination a bit, reader!)

Now the twist. Suppose some mathematically-minded geologist set out to prove that the two exquisite Caspian gems, plus the tiny round pearl, were sui generis — in other words, that there was a precise reason that no other gemstone or pearl of any type or size would ever again, or could ever again, be found in the Caspian Sea . Does seeking such a proof make any sense? How could there be a watertight scientific reason absolutely forbidding any gems — except for one pearl, one ruby, and one diamond — from ever being found on the floor of the Caspian Sea? It sounds absurd.

This is typical of how we think about the physical world — we think of it as being filled with contingent events, facts that could be otherwise, situations that have no fundamental reason for their being as they are. But let me remind you that mathematicians see their pristine, abstract world as the antithesis to the random, accident-filled physical world we all inhabit. Things that happen in the mathematical world strike mathematicians as happening, without any exceptions, for statable, understandable reasons.

This — the Mathematician’s Credo — is the mindset that you have to adopt and embrace if you wish to understand how mathematicians think. And in this particular case, the mystery of the lack of Fibonacci powers, although just a tiny one in most mathematicians’ eyes, was a particularly baffling one, because it seemed to offer no natural route of access. The two phenomena involved — integer powers with arbitrarily large exponents, on the one hand, and Fibonacci numbers on the other — simply seemed (like gemstones and the Caspian Sea) to be too conceptually remote from each other to have any deep, systematic, inevitable interrelationship.

And then along came a vast team of mathematicians who had set their collective bead on the “big game” of Fermat’s Last Theorem (the notorious claim, originally made by Pierre de Fermat in the middle of the seventeenth century, that no positive integers a, b, c exist such that a n + b n equals c n , with the exponent n being an integer greater than 2). This great international relay team, whose final victorious lap was magnificently sprinted by Andrew Wiles (his sprint took him about eight years), was at last able to prove Fermat’s centuries-old claim by using amazing techniques that combined ideas from all over the vast map of contemporary mathematics.

In the wake of this team’s revolutionary work, new paths were opened up that seemed to leave cracks in many famous old doors, including the tightly-closed door of the small but alluring Fibonacci power mystery. And indeed, roughly ten years after the proof of Fermat’s Last Theorem, a trio of mathematicians, exploiting the techniques of Wiles and others, were able to pinpoint the exact reason for which cubic 8 and square 144 will never have any perfect-power mates in Leonardo di Pisa’s recursive sequence (except for 1). Though extremely recondite, the reason behind the infinite mutual-avoidance dance had been found. This is just one more triumph of the Mathematician’s Credo — one more reason to buy a lot of stock in the idea that in mathematics, where there’s a pattern, there’s a reason.

A Tiny Spark in Gödel’s Brain

We now return to the story of Kurt Gödel and his encounter with the powerful idea that all sorts of infinite classes of numbers can be defined through various kinds of recursive rules. The image of the organic growth of an infinite structure or pattern, all springing out of a finite set of initial seeds, struck Gödel as much more than a mere curiosity; in fact, it reminded him of the fact that theorems in PM (like theorems in Euclid’s Elements ) always spring (by formal rules of inference) from earlier theorems in PM, with the exception of the first few theorems, which are declared by fiat to be theorems, and thus are called “axioms” (analogues to the seeds).

In other words, in the careful analogy sparked in Gödel’s mind by this initially vague connection, the axioms of PM would play the role of Fibonacci’s seeds 1 and 2, and the rules of inference of PM would play the role of adding the two most recent numbers. The main difference is that in PM there are several rules of inference, not just one, so at any stage you have a choice of what to do, and moreover, you don’t have to apply your chosen rule to the most recently generated theorem(s), so that gives you even more choice. But aside from these extra degrees of freedom, Gödel’s analogy was very tight, and it turned out to be immensely fruitful.

Clever Rules Imbue Inert Symbols with Meaning

I must stress here that each rule of inference in a formal system like PM not only leads from one or more input formulas to an output formula, but it does so by purely typographical means — that is, via purely mechanical symbol-shunting that doesn’t require any thought about the meanings of symbols. From the viewpoint of a person (or machine) following the rules to produce theorems, the symbols might as well be totally devoid of meaning.

On the other hand, each rule has to be very carefully designed so that, given input formulas that express truths, the output formula will also express a truth. The rule’s designer (Russell and Whitehead, in this case) therefore has to think about the symbols’ intended meanings in order to be sure that the rule will work exactly right for a manipulator (human or otherwise) who is not thinking about the symbols’ intended meanings.