Gödel, Escher, Bach: An Eternal Golden Braid (16 page)

We answered no to the artistic question, "Are all figures recursive We have now seen that we must likewise answer no to the analogous question in mathematics: "Are all sets recursive?" With this perspective, 1 us now come back to the elusive word "form".

Let us take our figure-set and our ground-set G again. We can agree that all the numbers in set have some common "form"-but can the same be said about numbers in s G? It is a strange question. When we are dealing with an infinite set to sta with-the natural numbers-the holes created by removing some subs may be very hard to define in any explicit way. And so it may be that th< are not connected by any common attribute or

"form". In the last analysis it is a matter of taste whether you want to use the word

"form"-but just thinking about it is provocative. Perhaps it is best not to define "form", bi to leave it with some intuitive fluidity.

Here is a puzzle to think about in connection with the above matter Can you characterize the following set of integers (or its negative space) 1

3

7

12

18

26

35

45

56

69...

How is this sequence like the FIGURE-FIGURE Figure?

Primes as Figure Rather than Ground

Finally, what about a formal system for generating primes? How is it don< The trick is to skip right over multiplication, and to go directly to
nondivisibility
as the thing to represent positively. Here are an axiom schema and rule for producing theorems which represent the notion that one number does not divide (
D N D
) another number exactly: AXIOM SCHEMA: xy
D N D
x where x and y are hyphen-strings.

For example -
---D N D--,
where x has been replaced by'--'and y by ‘---“.

RULE: If x
D N D
y is a theorem, then so is x
D N D
x y.

If you use the rule twice, you can generate this theorem:

-----D N D --------------

which is interpreted as "5 does not divide 12". But
---D N D------------
is not a theorem.

What goes wrong if you try to produce it?

Now in order to determine that a given number is prime, we have to build up some knowledge about its nondivisibility properties. In particular, we want to know that it is not divisible by 2 or 3 or 4, etc., all the way up to 1 less than the number itself. But we can't be so vague in formal systems as to say "et cetera". We must spell things out.

We would like to have a way of saying, in the language of the system, "the number Z is
divisor free
up to X", meaning that no number between 2 and X divides Z. This can be done, but there is a trick to it. Think about it if you want.

Here is the solution:

RULE: If
--D N D
z is a theorem, so is z
D F
--.

RULE: If z
D F
x is a theorem and also x-
D N D
z is a theorem, z
D F
x- is a theorem.

These two rules capture the notion of divisor freeness. All we need to do is to say that primes are numbers which are divisor-free up to 1 less than themselves: RULE: If z-
DF
z is a theorem, then
P
z- is a theorem.

Oh-let's not forget that 2 is prime!

Axiom:
P--.

And there you have it. The principle of representing primality formally is that there is a test for divisibility which can be done without any backtracking. You march steadily upward, testing first for divisibility by 2, then by 3, and so on. It is this "monotonicity" or unidirectionality-this absence of cross-play between lengthening and shortening, increasing and decreasing-that allows primality to be captured. And it is this potential complexity of formal systems to involve arbitrary amounts of backwards-forwards interference that is responsible for such limitative results as Gödel’s Theorem, Turing's Halting Problem, and the fact that not all recursively enumerable sets are recursive.

Contracrostipunctus

Achilles has come to visit his friend and jogging companion, the
Tortoise, at his home

Achilles: Heavens, you certainly have an admirable boomerang collection Tortoise: Oh, pshaw. No better than that of any other Tortoise. And now would you like to step into the parlor?

Achilles: Fine. (
Walks to the corner of the room
.) I see you also have a large collection of records. What sort of music do you enjoy?

Tortoise: Sebastian Bach isn't so bad, in my opinion. But these days, I must say, I am developing more and more of an interest in a rather specialized sort of music.

Achilles: Tell me, what kind of music is that?

Tortoise: A type of music which you are most unlikely to have heard of. call it "music to break phonographs by".

Achilles: Did you say "to break phonographs by"? That is a curious concept. I can just see you, sledgehammer in hand, whacking on phonograph after another to pieces, to the strains of Beethoven's heroic masterpiece
Wellington's Victory
.

Tortoise: That's not quite what this music is about. However, you might find its true nature just as intriguing. Perhaps I should give you a brief description of it?

Achilles: Exactly what I was thinking.

Tortoise: Relatively few people are acquainted with it. It all began whet my friend the Crab-have you met him, by the way?-paid m• a visit.

Achilles: ' twould be a pleasure to make his acquaintance, I'm sure Though I've heard so much about him, I've never met him

Tortoise: Sooner or later I'll get the two of you together. You'd hit it of splendidly.

Perhaps we could meet at random in the park on day ...

Achilles: Capital suggestion! I'll be looking forward to it. But you were going to tell me about your weird "music to smash phone graphs by", weren't you?

Tortoise: Oh, yes. Well, you see, the Crab came over to visit one day. You must understand that he's always had a weakness for fang gadgets, and at that time he was quite an aficionado for, of al things, record players. He had just bought his first record player, and being somewhat gullible, believed every word the salesman had told him about it-in particular, that it was capable of reproducing any and all sounds. In short, he was convinced that it was a Perfect phonograph.

Achilles: Naturally, I suppose you disagreed.

Tortoise: True, but he would hear nothing of my arguments. He staunchly maintained that any sound whatever was reproducible on his machine. Since I couldn't convince him of the contrary, I left it at that. But not long after that, I returned the visit, taking with me a record of a song which I had myself composed. The song was called "I Cannot Be Played on Record Player 1".

Achilles: Rather unusual. Was it a present for the Crab?

Tortoise: Absolutely. I suggested that we listen to it on his new phonograph, and he was very glad to oblige me. So he put it on. But unfortunately, after only a few notes, the record player began vibrating rather severely, and then with a loud "pop", broke into a large number of fairly small pieces, scattered all about the room. The record was utterly destroyed also, needless to say.

Achilles: Calamitous blow for the poor fellow, I'd say. What was the matter with his record player?

Tortoise: Really, there was nothing the matter, nothing at all. It simply couldn't reproduce the sounds on the record which I had brought him, because they were sounds that would make it vibrate and break.

Achilles: Odd, isn't it? I mean, I thought it was a Perfect phonograph. That's what the salesman had told him, after all.

Tortoise: Surely, Achilles, you don't believe everything that salesmen tell you! Are you as naive as the Crab was?

Achilles: The Crab was naiver by far! I know that salesmen are notorious prevaricators. I wasn't born yesterday!

Tortoise: In that case, maybe you can imagine that this particular salesman had somewhat exaggerated the quality of the Crab's piece of equipment ... perhaps it was indeed less than Perfect, and could not reproduce every possible sound.

Achilles: Perhaps that is an explanation. But there's no explanation for the amazing coincidence that your record had those very sounds on it ...

Tortoise: Unless they got put there deliberately. You see, before returning the Crab's visit, I went to the store where the Crab had bought his machine, and inquired as to the make. Having ascertained that, I sent off to the manufacturers for a description of its design. After receiving that by return mail, I analyzed the entire construction of the phonograph and discovered a certain set of sounds which, if they were produced anywhere in the vicinity, would set the device to shaking and eventually to falling apart.

Achilles: Nasty fellow! You needn't spell out for me the last details: that you recorded those sounds yourself, and offered the dastardly item as a gift ...

Tortoise: Clever devil! You jumped ahead of the story! But that wasn't t end of the adventure, by any means, for the Crab did r believe that his record player was at fault. He was quite stubborn. So he went out and bought a new record player, this o even more expensive, and this time the salesman promised give him double his money back in case the Crab found a soul which it could not reproduce exactly.

So the Crab told r excitedly about his new model, and I promised to come over and see it.

Achilles: Tell me if I'm wrong-I bet that before you did so, you on again wrote the manufacturer, and composed and recorded new song called "I Cannot Be Played on Record Player based on the construction of the new model.

Tortoise: Utterly brilliant deduction, Achilles. You've quite got the spirit.

Achilles: So what happened this time?

Tortoise: As you might expect, precisely the same thing. The phonograph fell into innumerable pieces, and the record was shattered. Achilles: Consequently, the Crab finally became convinced that there could be no such thing as a Perfect record player.

Tortoise: Rather surprisingly, that's not quite what happened. He was sure that the next model up would fill the bill, and having twice the money, h e--

Achilles: Oho-I have an idea! He could have easily outwitted you, I obtaining a LOW-fidelity phonograph-one that was not capable of reproducing the sounds which would destroy it. In that way, he would avoid your trick.

Tortoise: Surely, but that would defeat the-original purpose-namely, to have a phonograph which could reproduce any sound whatsoever, even its own self-breaking sound, which is of coup impossible.

Achilles: That's true. I see the dilemma now. If any record player-si Record Player X-is sufficiently high-fidelity, then when attempts to play the song "I Cannot Be Played on Record Player X", it will create just those vibrations which will cause to break. .. So it fails to be Perfect. And yet, the only way to g, around that trickery, namely for Record Player X to be c lower fidelity, even more directly ensures that it is not Perfect It seems that every record player is vulnerable to one or the other of these frailties, and hence all record players are defective.

Tortoise: I don't see why you call them "defective". It is simply an inherent fact about record players that they can't do all that you might wish them to be able to do. But if there is a defect anywhere, is not in THEM, but in your expectations of what they should b able to do! And the Crab was just full of such unrealistic expectations.

Achilles: Compassion for the Crab overwhelms me. High fidelity or low fidelity, he loses either way.

Tortoise: And so, our little game went on like *_his for a few more rounds, and eventually our friend tried to become very smart. He got wind of the principle upon which I was basing my own records, and decided to try to outfox me. He wrote to the phonograph makers, and described a device of his own invention, which they built to specification. He called it "Record Player Omega". It was considerably more sophisticated than an ordinary record player.

Achilles: Let me guess how: Did it have no of cotton? Or

Tortoise: Let me tell you, instead. That will save some time. In the first place, Record Player Omega incorporated a television camera whose purpose it was to scan any record before playing it. This camera was hooked up to a small built-in computer, which would determine exactly the nature of the sounds, by looking at the groove-patterns.

Achilles: Yes, so far so good. But what could Record Player Omega do with this information?

Tortoise: By elaborate calculations, its little computer figured out what effects the sounds would have upon its phonograph. If it deduced that the sounds were such that they would cause the machine in its present configuration to break, then it did something very clever. Old Omega contained a device which could disassemble large parts of its phonograph subunit, and rebuild them in new ways, so that it could, in effect, change its own structure. If the sounds were "dangerous", a new configuration was chosen, one to which the sounds would pose no threat, and this new configuration would then be built by the rebuilding subunit, under direction of the little computer. Only after this rebuilding operation would Record Player Omega attempt to play the record.

Achilles: Aha! That must have spelled the end of your tricks. I bet you were a little disappointed.