I Am a Strange Loop - Douglas R. Hofstadter [87]
Although it might seem an odd thing to do, one could certainly pose eighteenth-century–style number-theory questions such as, “Which integers are expressible as the sum of two prim numbers, and which integers are not?” Probably nobody would ever seriously ask such an oddball question, but the point is that the property of being a prim number, although it’s a rather arcane “modern” property, is no more and no less a genuinely number-theoretical property of an integer than is a “classical” property, such as being square or being prime or being a Fibonacci number.
The Uncanny Power of Prim Numbers
Suppose someone told you that they had built a machine — I’ll dub it “Guru” — that would always correctly answer any question of the form “Is n a prime number?”, with n being any integer that you wish. When asked, “Is 641 prime?”, Guru would spin its wheels for a bit and then say “yes”. As for 642, Guru would “think” a little while and then say “no”. I suppose you would not be terribly surprised by such a machine. That such a machine can be realized, either in silicon circuitry on in domino-chain technology, is not anything to boggle anyone’s mind in this day and age.
But suppose someone told you that they had built an analogous machine — I’ll dub it “Göru” — that would always correctly answer any question of the form “Is n a prim number?” Would this claim — strictly analogous to the previous one — strike you as equally ho-hum? If so, then I respectfully submit that you’ve got another think coming.
The reason is this. If you believed Göru to be reliable and you also believed in the Mathematician’s Credo (Principia Mathematica version), then you could conclude that your little Göru, working all by itself, could answer any number-theoretical question that you were interested in, just like a genie conjured from a magic lamp. How so? What makes Göru a magic genie?
Well, suppose you wanted to know if statement X is true or false (for instance, the famous claim “Every even number greater than 2 is the sum of two primes” — which, as I stated above, remains unsettled even today, after nearly three centuries of work). You would just write X down in the formal notation of PM, then convert that formula mechanically into its Gödel number x, and feed that number into Göru (thus asking if x is prim or not). Of course x will be a huge integer, so it would probably take Göru a good while to give you an answer, but (assuming that Göru is not a hoax) sooner or later it would spit out either a “yes” or a “no”. In case Göru said “yes”, you would know that x is a prim number, which tells you that the formula it encodes is a provable formula, which means that statement X is true. Conversely, were Göru to tell you “no”, then you would know that the statement X is not provable, and so, believing in the Mathematician’s Credo (Principia Mathematica version), you would conclude it is false.
In other words, if we only had a machine that could infallibly tell apart prim numbers and “saucy” (non-prim) numbers, and taking for granted that the Principia Mathematica version of the Mathematician’s Credo is valid, then we could infallibly tell true statements from false ones. In short, having a Göru would give us a royal key to all of mathematical knowledge.
The prim numbers alone would therefore seem to contain, in a cloaked fashion, all of mathematical knowledge wrapped up inside them! No other sequence of numbers ever dreamt up by anyone before Gödel had anything like this kind of magically oracular quality. These amazing numbers seem to be worth their weight in gold! But as I told you, the prim numbers are elusive, because small ones sometimes wind up being added to the club at very late stages, so it won’t be easy to tell prim numbers from saucy ones, nor to build a Göru. (This is meant as a premonition of things to come.)
Gödelian Strangeness
Finally, Gödel carried his analogy to its inevitable, momentous conclusion, which was to spell out for his readers (not symbol by symbol, of course, but via a precise set