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

Tortoise: Good idea. (Scrambles in behind the dresser.) Achilles: Who's there?

Voice: Open up-it's the cops.

Achilles: Come in, it's open.

(Two burly policemen walk in, wearing shiny badges.)

Cop: I'm Silva. This is Gould. (Points at his badge.) Is there an Achilles at this address?

Achilles: That's me!

Cop: Well, Achilles, we have reason to believe that there is a very gold Asian box here, filled with one hundred Louis d'or. Someone absconded with it from the museum this afternoon. Achilles: Heavens to Betsy!

Cop: If it is here, Achilles, since you would be the only possible suspect, I' regret to say that I should have to take you into custody. Now I have here a search warrant Achilles: Oh, sirs, am I ever glad you arrived! All evening long, I have been being terrorized by Mr. Tortoise and his very Asian gold box. Now at last you have come to liberate me! Please, sirs, just take a look behind that dresser, and there you will find the culprit!

(The cops look behind the dresser and spy the Tortoise huddled behind it, holding
his very gold Asian box, and trembling.)

Cop: So there it is! And so Mr. Tortoise is the varmint, eh? I never would have suspected HIM. But he's caught, red-handed.

Achilles: Haul the villain away, kind sirs! Thank goodness, that's the last I'll have to hear of him, and the Very Asian Gold Box!

Self-Awareness and Chaos

BLOOP, FLOOP, AND GLOOP
are not trolls, talking ducks, or the sounds made by a sinking ship-they are three computer languages, each one with is own special purpose.

These languages were invented specially for this chapter. They will be of use in explaining some new senses of the word 'recursive -in particular, the notions of
primitive
recursivity
and
general recursivity
. They will prove very helpful in clarifying the machinery of self-reference in
TNT
.

We seem to be making a rather abrupt transition from brains and hinds to technicalities of mathematics and computer science. Though the transition is abrupt in some ways, it makes some sense. We just saw how a certain kind of self-awareness seems to be at the crux of consciousness. Vow we are going to scrutinize "self-awareness" in more formal settings, such as
TNT
. The gulf between
TNT
and a mind is wide, but some of the ideas will be most illuminating, and perhaps metaphorically transportable back to our thoughts about consciousness.

One of the amazing things about
TNT's
self-awareness is that it is intimately connected to questions about order versus chaos among the natural numbers. In particular, we shall see that an orderly system of sufficient complexity that it can mirror itself cannot be
totally
orderly-it must contain some strange, chaotic features. For readers who have some Achilles in them, this will be hard to take. However, there is a "magical"

compensation: there is a kind of order to the disorder, which is now its own field of study, called "recursive function theory". Unfortunately, we will not be able to do much more than hint at the fascination of this subject.

Representability and Refrigerators

Phrases such as "sufficiently complex", "sufficiently powerful" and the like lave cropped up quite often earlier. Just what do they mean? Let us go back to the battle of the Crab and Tortoise, and ask, "What qualifies something as a record player?" The Crab might claim that his refrigerator s a "Perfect" record player. Then to prove it, he could set any record whatsoever atop it, and say, "You see-it's playing it!" The Tortoise, if he wanted to counter this Zen-like act, would have to reply, "No-your refrigerator is too low-fidelity to be counted as a phonograph: it cannot reproduce sounds-at all (let alone its self-breaking sound)." The Tortoise

can only make a record called "I Cannot Be Played on Record Player X" provided that Record Player X is really a record player! The Tortoise's method is quite insidious, as it plays on the strength, rather than on the weakness, of the system. And therefore he requires "sufficiently hi-fi" record players.

Ditto for formal versions of number theory. The reason that
TNT
is a formalization of N is that its symbols act the right way: that is, its theorems are not silent like a refrigerator-they speak actual truths of N. Of course, so do the theorems of the pqsystem. Does it, too, count as "a formalization of number theory", or is it more like a refrigerator? Well, it is a little better than a refrigerator, but it is still pretty weak. The pqsystem does not include enough of the core truths of N to count as "a number theory".

What, then, are these "core truths" of
N
? They are the
primitive recursive truths
; that means they involve only
predictably terminating
calculations. These core truths serve for
N
as Euclid's first four postulates served for geometry: they allow you to throw out certain candidates before the game begins, on the grounds of "insufficient power".

From here on out, the
representability of all primitive recursive truths
will be the criterion for calling a system "sufficiently powerful".

Ganto's Ax in Metamathematics

The significance of the notion is shown by the following key fact: If you have a sufficiently powerful formalization of number theory, then Gödel’s method is applicable, and consequently your system is
incomplete
. If, on the other hand, your system is
not
sufficiently powerful (i.e., not all primitive recursive truths are theorems), then your system is, precisely by virtue of that lack,
incomplete
. Here we have a reformulation of

"Ganto's Ax" in metamathematics: whatever the system does, Gödel’s Ax will chop its head off! Notice also how this completely parallels the high-fidelity-versus-low fidelity battle in the
Contracrostipunctus
.

Actually, it turns out that much weaker systems are still vulnerable to the Gödel method; the criterion that all primitive recursive truths need be represented as theorems is far too stringent. It is a little like a thief who will only rob "sufficiently rich" people, and whose criterion is that the potential victim should be carrying at least a million dollars in cash.

In the case of
TNT
, luckily, we will be able to act in our capacity as thieves, for the million in cash is there-which is to say,
TNT
does indeed contain all primitive recursive truths as theorems.

Now before we plunge into a detailed discussion of primitive recursive functions and predicates, I would like to tie thee themes of this Chapter to themes from earlier Chapters, so as to provide a bit better motivation.

Finding Order by Choosing the Right Filter

We saw at a very early stage that formal systems can be difficult and unruly beasts because they have lengthening and shortening rules, which can

possibly lead to never-ending searches among strings. The discovery of Gödel-numbering showed that any search for a string having a special typographical property has an arithmetical cousin: an isomorphic search for an integer with a corresponding special arithmetical property. Consequently, the quest for decision procedures for formal systems involves solving the mystery of unpredictably long searches-
chaos
-among the integers.

Now in the
Aria with Diverse Variations
, I gave perhaps too much weight to apparent manifestations of chaos in problems about integers. As a matter of fact, people have tamed wilder examples of apparent chaos than the "wondrousness" problem, finding them to be quite gentle beasts after all. Achilles' powerful faith in the regularity and predictability of numbers should therefore be accorded quite a bit of respect-especially as it reflects the beliefs of nearly all mathematicians up till the 1930's. To show why order versus chaos is such a subtle and significant issue, and to tie it in with questions about the location and revelation of meaning, I would like to quote a beautiful and memorable passage from
Are Quanta Real
?-a Galilean Dialogue by the late J. M. Jauch: SALVIATI Suppose I give you two sequences of numbers, such as

78539816339744830961566084...

And

1, -1/3, +1/5, -1/7, +1/9, -1/11, +1/13, -1/15, ...

If I asked you, Simplicio, what the next number of the first sequence is, what would you say?

SIMPLICIO I could not tell you. I think it is a random sequence and that there is no law in it.

SALVIATI And for the second sequence?

SIMPLICIO That would be easy. It must be +1/17.

SALVIATI Right. But what would you say if I told you that the first sequence is also constructed by a law and this law is in fact identical with the one you have just discovered for the second sequence? SIMPLICIO This does not seem probable to me.

SALVIATI But it is indeed so, since the first sequence is simply the beginning of the decimal fraction [expansion] of the sum of the second. Its value is Tr/4.

SIMPLICIO You are full of such mathematical tricks, but I do not see what this has to do with abstraction and reality.

SALVIATI The relationship with abstraction is easy to see. The first sequence looks random unless one has developed through a process of abstraction a kind of filter which sees a simple structure behind the apparent randomness.

It is exactly in this manner that laws of nature are discovered. Nature presents us with a host of phenomena which appear mostly as chaotic randomness until we select some significant events, and abstract from their particular, irrelevant circumstances so that they become idealized. Only then can they exhibit their true structure in full splendor.

SAGREDO This is a marvelous idea! It suggests that when we try to understand nature, we should look at the phenomena as if they were
messages
to be understood. Except that each message appears to be random until we establish a code to read it. This code takes the form of an abstraction, that is, we choose to ignore certain things as irrelevant and we thus partially select the content of the message by a free choice. These irrelevant signals form the "background noise," which will limit the accuracy of our message.

But since the code is not absolute there may be several messages in the same raw material of the data, so changing the code will result in a message of' equally deep significance in something that was merely noise before, and conversely: In a new code a former message may be devoid of meaning.

Thus a code presupposes a free choice among different, complementary aspects, each of which has equal claim to
reality
, if I may use this dubious word.

Some of these aspects may be completely unknown to us now but they may reveal themselves to an observer with a different system of abstractions.

But tell me, Salviati, how can we then still claim that we
discover
something out there in the objective real world? Does this not mean that we are merely creating things according to our own images and that reality is only within ourselves?

SALVIATI I don't think that this is necessarily so, but it is a question which requires deeper reflection.'

Jauch is here dealing with messages that come not from a "sentient being" but from nature itself. The questions that we raised in Chapter VI on the relation of meaning to messages can be raised equally well with messages from nature. Is nature chaotic, or is nature patterned? And what is the role of intelligence in determining the answer to this question?

To back off from the philosophy, however, we can consider the point about the deep regularity of an apparently random sequence. Might the function
Q
(n) from Chapter V have a simple, nonrecursive explanation, too? Can every problem, like an orchard, be seen from such an angle that its secret is revealed? Or are there some problems in number theory which, no matter what angle they are seen from, remain mysteries?

With this prologue, I feel it is time to move ahead to define the precise meaning of the term "predictably long search". This will be accomplished in terms of the language B1ooP.

Primordial Steps of the Language BlooP

Our topic will be searches for natural numbers which have various properties. In order to talk about the
length
of any search, we shall have to define some primordial
steps
, out of which all searches are built, so that length can be measured in terms of number of steps.

Some steps which we might consider primordial are:

adding any two natural numbers;

multiplying any two natural numbers;

determining if two numbers are equal;

determining the larger (smaller) of two numbers.

Loops and Upper Bounds

If we try to formulate a test for, say, primality in terms of such steps, we shall soon see that we have to include a
control structure
-that is, descriptions of the order to do things in, when to branch back and try something again, when to skip over a set of steps, when to stop, and similar matters.

It is typical of any
algorithm
-that is, a specific delineation of how to carry out a task-that it includes a mixture of (1) specific operations to be performed, and (2) control statements. Therefore, as we develop our language for expressing predictably long calculations, we shall have to incorporate primordial control structures also. In fact, the hallmark of BlooP is its limited set of control structures. It does not allow you to branch to arbitrary steps, or to repeat groups of steps without limit; in BlooP, essentially the only control structure is the bounded loop: a set of instructions which can be executed over and over again, up to a predefined maximum number of times, called the
upper bound
, or
ceiling
, of the loop. If the ceiling were 300, then the loop might be executed 0, 7, or 300