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

Achilles: Certainly.

Tortoise: The first type of search-the non-chaotic type-is exemplified by the test involved in checking for the Goldbach property. You just look at primes less than 2N, and if some pair adds up to 2N, then 2N has the Goldbach property; otherwise, it doesn't.

This kind of test is not only sure to terminate, but you can predict BY "'HEN it will terminate, as well.

Achilles: So it is a PREDICTABLY TERMINATING test. Are you going to tell me that checking for some number-theoretical properties involves tests which are guaranteed to terminate, but about which there is no way to know in advance how long they will take?

Tortoise: How prophetic of you, Achilles. And the existence of such tests shows that there is intrinsic chaos, in a certain sense, in the natural number system.

Achilles: Well, in that case, I would have to say that people just don't know enough about the test. If they did a little more research, they could figure out how long it will take, at most, before it terminates. After all, there must always be some rhyme or reason to the patterns among integers. There can't just be chaotic patterns which defy prediction'

Tortoise: I can understand your intuitive faith, Achilles. However, it's not always justified. Of course, in many cases you are exactly right just because somebody doesn't know something, one can't conclude that it is unknowable' But there are certain properties of integers for which terminating tests can be proven to exist, and yet about which it can also be PROVEN that there is no way to predict in advance how long they will take.

Achilles: I can hardly believe that. It sounds as if the devil himself managed to sneak in and throw a monkey wrench into God's beautiful realm of natural numbers'

Tortoise: Perhaps it will comfort you to know that it is by no means easy, or natural, to define a property for which there is a terminating but not PREDICTABLY

terminating test. Most "natural" properties of integers do admit of predictably terminating tests. For example, primeness. squareness, being a power of ten, and so on.

Achilles: Yes, I can see that those properties are completely straightforward to test for.

Will you tell me a property for which the only possible test is a terminating but nonpredictable one?

Tortoise: That's too complicated for me in my sleepy state. Let me instead show you a property which is very easy to define, and yet for which no terminating test is known. I'm not saying there won't ever be one discovered, mind you just that none is known. You begin with a number-would you care to pick one?

Achilles: How about 15?

Tortoise: An excellent choice. We begin with your number, and if it is ODD, we triple it, and add 1. If it is EVEN, we take half of it. Then we repeat the process. Call a number which eventually reaches 1 this way a WONDROUS number, and a number which doesn't, an UNWONDROUS number

Achilles: Is 15 wondrous, or unwondrous? Let's see:

15 is ODD, so I make 3n + 1:

46

46 is EVEN, so I take half:

23

23 is ODD, so I make 3n + 1:

70

70 is EVEN, so I take half:

35

35 is ODD, so I make 3n + 1:

106

106 is EVEN, so I take half:

53

53 is ODD, so I make 3n + 1:

160

160 is EVEN, so I take half:

80

80 is EVEN, so I take half:

40

40 is EVEN, so I take half:

20

20 is EVEN, so I take half:

10

10 is EVEN, so I take half:

5

5 is ODD, so I make 3n + 1:

16

16 is EVEN, so I take half:

8

8 is EVEN, so I take half:

4

4 is EVEN, so I take half:

2

2 is EVEN, so I take half:

1

.

Wow! That's quite a roundabout journey, from 15 to 1. But I finally reached it. That shows that 15 has the property of being wondrous. I wonder what numbers are UNwondrous ...

Tortoise: Did you notice how the numbers swung up and down, in this simply defined process?

Achilles: Yes. I was particularly surprised, after thirteen turns, to find myself at 16, only one greater than 15, the number I started with. In one sense, I was almost back where I started-yet in another sense, I' was nowhere near where I had started. Also, I found it quite curious that I had to go as high as 160 to resolve the question. I wonder how come.

Tortoise: Yes, there is an infinite "sky" into which you can sail, and it is very hard to know in advance how high into the sky you will wind up sailing. Indeed, it is quite plausible that you might just sail up and up and up, and never come down.

Achilles: Really? I guess that is conceivable-but what a weird coincidence it would require! You'd just have to hit odd number after odd number, with only a few evens mixed in. I doubt if that would ever happen-but I just don't know for sure.

Tortoise: Why don't you try starting with 27? Mind you, I don't promise anything. But sometime, just try it, for your amusement. And I'd advise you to bring along a rather large sheet of paper.

Achilles: Hmm ... Sounds interesting. You know, it still makes me feel funny to associate the wondrousness (or unwondrousness) with the starting number, when it is so obviously a property of the entire number system.

Tortoise: I understand what you mean, but it's not that different from saying “29 is prime” or “gold is valuable” – both statements attribute to

a single entity a property which it has only by virtue of being embedded in a particular context.

Achilles: I suppose you're right. This "wondrousness" problem is wondrous tricky, because of the way in which the numbers oscillate-now increasing, now decreasing.

The pattern OUGHT to be regular,-yet on the surface it appears to be quite chaotic.

Therefore, I can well imagine why, as of yet, no one knows of a test for the property of wondrousness which is guaranteed to terminate.

Tortoise: Speaking of terminating and nonterminating processes, and those which hover in between, I am reminded of a friend of mine, an author, who is at work on a book.

Achilles: Oh, how exciting! What is it called?

Tortoise: Copper, Silver, Gold: an Indestructible Metallic Alloy. Doesn't that sound interesting?

Achilles: Frankly, I'm a little confused by the title. After all, what do Copper, Silver, and Gold have to do with each other? Tortoise: It seems clear to me.

Achilles: Now if the title were, say, Giraffes, Silver, Gold, or Copper, Elephants, Gold, why, I could see it .. .

Tortoise: Perhaps you would prefer Copper, Silver, Baboons?

Achilles: Oh, absolutely! But that original title is a loser. No one would understand it.

Tortoise: I'll tell my friend. He'll be delighted to have a catchier title (as will his publisher).

Achilles: I'm glad. But how were you reminded of his book by our discussion?

Tortoise: Ah, yes. You see, in his book there will be a Dialogue in which he wants to throw readers off by making them SEARCH for the ending.

Achilles: A funny thing to want to do. How is it done?

Tortoise: You've undoubtedly noticed how some authors go to so much trouble to build up great tension a few pages before the end of their stories-but a reader who is holding the book physically in his hands can FEEL that the story is about to end.

Hence, he has some extra information which acts as an advance warning, in a way.

The tension is a bit spoiled by the physicality of the book. It would be so much better if, for instance, there were a lot of padding at the end of novels.

Achilles: Padding?

Tortoise: Yes; what I mean is, a lot of extra printed pages which are not part of the story proper, but which serve to conceal the exact location of the end from a cursory glance, or from the feel of the book.

Achilles: I see. So a story's true ending might occur, say, fifty or a hundred pages before the physical end of the book?

Tortoise: Yes. This would provide an element of surprise, because the reader wouldn't know in advance how many pages are padding, and how many are story.

Achilles: If this were standard practice, it might be quite effective. But there is a problem. Suppose your padding were very obvious-such as a lot of blanks, or pages covered with X's or random letters. Then, it would be as good as absent.

Tortoise: Granted. You'd have to make it resemble normal printed pages.

Achilles: But even a cursory glance at a normal page from one story will often suffice to distinguish it from another story. So you will have to make the padding resemble the genuine story rather closely.

Tortoise: That's quite true. The way I've always envisioned it is this: you bring the story to an end; then without any break, you follow it with something which looks like a continuation but which is in reality just padding, and which is utterly unrelated to the true theme. The padding is, in a way, a "post-ending ending". It may contain extraneous literary ideas, having little to do with the original theme.

Achilles: Sneaky! But then the problem is that you won't be able to tell when the real ending comes. It'll just blend right into the padding.

Tortoise: That's the conclusion my author friend and I have reached as well. It's a shame, for I found the idea rather appealing.

Achilles: Say, I have a suggestion. The transition between genuine story and padding material could be made in such a way that, by sufficiently assiduous inspection of the text, an intelligent reader will be able to detect where one leaves off and the other begins. Perhaps it will take him quite a while. Perhaps there will be no way to predict how long it will take ... But the publisher could give a guarantee that a sufficiently assiduous search for the true ending will always terminate, even if he can't say how long it will be before the test terminates.

Tortoise: Very well-but what does "sufficiently assiduous" mean?

Achilles: It means that the reader must be on the lookout for some small but telltale feature in the text which occurs at some point. That would signal the end. And he must be ingenious enough to think up, and hunt for, many such features until he finds the right one.

Tortoise: Such as a sudden shift of letter frequencies or word lengths? Or a rash of grammatical mistakes?

Achilles: Possibly. Or a hidden message of some sort might reveal the true end to a sufficiently assiduous reader. Who knows? One could even throw in some extraneous characters or events which are inconsistent with the spirit of the foregoing story. A naive reader would swallow the whole thing, whereas a sophisticated reader would be able to spot the dividing line exactly.

Tortoise: That's a most original idea, Achilles. I'll relay it to my friend, and perhaps he can incorporate it in his Dialogue.

Achilles: I would be highly honored.

Tortoise: Well, I am afraid that I myself am growing a little groggy, Achilles. It would be well for me to take my leave, while I am still capable of navigating my way home.

Achilles: I am most flattered' that you have stayed up for so long, and at such an odd hour of the night, just for my benefit. I assure you that

your number-theoretical entertainment has been a perfect antidote to my usual tossing and turning. And who knows-perhaps I may even be able to go to sleep tonight. As a token of my gratitude, Mr. T, I would like to present you with a special gift.

Tortoise: Oh, don't be silly, Achilles.

Achilles: It is my pleasure, Mr. T. Go over to that dresser; on it, you will see an Asian box.

(The Tortoise moseys over to Achilles' dresser.)

Tortoise. You don't mean this very gold Asian box, do you?

Achilles: That's the one. Please accept it, Mr. T, with my warmest compliments.

Tortoise: Thank you very much indeed, Achilles. Hmm ... Why are all these mathematicians' names engraved on the top? What a curious list:

D
e Morgan

A
b
el

Bo
o
le

Br o
u
w e r

S i e r
p
i n s k i

W e i e r
s
t r a s s

Achilles: I believe it is supposed to be a Complete List of All Great Mathematicians.

What I haven't been able to figure out is why the letters running down the diagonal are so much bolder.

Tortoise: At the bottom it says, "Subtract 1 from the diagonal, to find Bach in Leipzig".

Achilles: I saw that, but I couldn't make head or tail of it. Say, how about a shot of excellent whiskey? I happen to have some in that decanter on my shelf.

Tortoise: No, thanks. I'm too tired. I'm just going to head home. (Casually, he opens the box.) Say, wait a moment, Achilles-there are one hundred Louis d'or in here!

Achilles: I would be most pleased if you would accept them, Mr. T. Tortoise: But-but Achilles: No objections, now. The box, the gold-they're yours. And thank you for an evening without parallel.

Tortoise: Now whatever has come over you, Achilles? Well, thank you for your outstanding generosity and I hope you have sweet dreams about the strange Goldbach Conjecture, and its Variation. Good night.

(And he picks up the very gold Asian box filled with the one hundred Louis d'or, and
walks towards the door. As he is about to leave, there is a loud knock.)
Who could be knocking at this ungodly hour, Achilles?

Achilles: I haven't the foggiest idea. It seems suspicious to me. Why don't you go hide behind the dresser, in case there's any funny business.