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

The self-reference of this sentence is achieved in a more direct way than in the Epimenides paradox; less hidden processing is needed. By the way, it is interesting to point out that the phrase "this sentence" appears in the previous sentence; yet it is not there to cause selfreference: you probably understood that its referent was the Quine sentence, rather than the sentence in which it occurs. This just goes to show how pointer phrases such as "this sentence" are interpreted according to context, and helps to show that the processing of such phrases is indeed quite involved.

A Self-Reproducing Program

The notion of quining, and its usage in creating self-reference, have already been explained inside the Dialogue itself, so we need not dwell on such matters here. Let us instead show how a computer program can use precisely the same technique to reproduce itself. The following selfreproducing program is written in a BlooP-like language and is based on following a phrase by its own quotation (the opposite order from quining, so I reverse the name "quine" to make "eniuq"):

DEFINE PROCEDURE "ENIUQ" [TEMPLATE]: PRINT [TEMPLATE, LEFT-BRACKET, QUOTE-MARK, TEMPLATE, QUOTE-MARK, RIGHT-BRACKET,

PERIOD].

ENIUQ

['DEFINE PROCEDURE "ENIUQ" [TEMPLATE]: PRINT [TEMPLATE, LEFT-BRACKET, QUOTE-MARK, TEMPLATE, QUOTE-MARK, RIGHT-BRACKET,

PERIOD]. ENIUQ'].

ENIUQ
is a procedure defined in the first two lines, and its input is called "
TEMPLATE
". It is understood that when the procedure is called,
TEMPLATE's
value will be some string of typographical characters. The effect of
ENIUQ
is to carry out a printing operation, in which TEMPLATE gets printed twice: the first time just plain; the second time wrapped in (single) quotes and brackets, and garnished with a final period. Thus, if
TEMPLATE's
value were the string
DOUBLE-BUBBLE
, then performing
ENIUQ
on it would yield:

DOUBLE-BUBBLE ['DOUBLE-BUBBLE'].

Now in the last four lines of the program above, the procedure
ENIUQ
is called with a specific value of
TEMPLATE
-namely the long string inside the single quotes:
DEFINE
...

ENIUQ
. That value has been carefully chosen; it consists of the definition of
ENIUQ
, followed by the word
ENIUQ
. This makes the program itself-or, if you prefer, a perfect copy of it-get printed out. It is very similar to Quine's version of the Epimenides sentence:

"yields falsehood when preceded by its quotation"

yields falsehood when preceded by its quotation.

It is very important to realize that the character string which appears n quotes in the last three lines of the program above-that is, the value of

TEMPLATE
-is never interpreted as a sequence of instructions. That it happens to be one is, in a sense. just an accident. As was pointed out above, it could just as well have been
DOUBLE-BUBBLE
or any other string of characters. The beauty of the scheme is that when the same string appears in the top two lines of this program, it is treated as a program (because it is not in quotes). Thus in this program, one string functions in two ways: first as program, and second as data. This is the secret of self-reproducing programs, and, as we shall see, of self-reproducing molecules. It is useful, incidentally, to call any kind of self-

•reproducing object or entity a
self-rep
; and likewise to call any self-referring object or entity a
self-ref
. I will use those terms occasionally from here on.

The preceding program is an elegant example of a self-reproducing program written in a language which was not designed to make the writing of self-reps particularly easy.

Thus, the task had to be carried out using those notions and operations which were assumed to be part of the language-such as the word
QUOTE-MARK
, and the command
PRINT
. But suppose a language were designed expressly for making self-reps easy to write. Then one could write much shorter self-reps. For example, suppose that the operation of eniuq-ing were a built-in feature of the language, needing no explicit definition (as we assumed PRINT

was). Then a teeny self-rep would be this:

ENIUQ ['ENIUQ'].

It is very similar to the Tortoise's version of Quine's version of the Epimenides self-ref, where the verb "to quine" is assumed to be known:

"yields falsehood when quined" yields falsehood when quined But self-reps can be even shorter. For instance, in some computer language it might be a convention that any program whose first symbol is an asterisk is to be copied before being executed normally. Then the program consisting of merely one asterisk is a self-rep!

You may complain that this is silly and depends on a totally arbitrary convention. In doing so, you are echoing my earlier point that it is almost cheating to use the phrase "this sentence" to achieve self-reference-it relies too much on the processor, and not enough on explicit directions for self-reference. Using an asterisk as an example of a self-rep is like using the word "I" as an example of a self-ref: both conceal all the interesting aspects of their respective problems.

This is reminiscent of another curious type of self-reproduction: via photocopy machine. It might be claimed that any written document is a self-rep because it can cause a copy of itself to be printed when it is placed in a photocopy machine and the appropriate button is pushed. But somehow this violates our notion of self-reproduction; the piece of paper is not consulted at all, and is therefore not directing its own reproduction. Again, everything is in the processor. Before we call something a self-rep, we want to have the feeling that, to the maximum extent possible, it explicitly contains the directions for copying itself.

To be sure, explicitness is a matter of degree; nonetheless there is an intuitive borderline on one side of which we perceive true self-directed self-reproduction, and on the other side of which we merely see copying being carried out by an inflexible and autonomous copying machine.

What Is a Copy?

Now in any discussion of self-refs and self-reps, one must sooner or later come to grips with the essential issue: what is a copy? We already dealt with that question quite seriously in Chapters V and VI; and now we come back to it. To give the flavor of the issue, let us describe some highly fanciful, yet plausible, examples of self-reps.

A Self-Reproducing Song

Imagine that there is a nickelodeon in the local bar which, if you press buttons 11-U, will play a song whose lyrics go this way:

Put another nickel in, in the nickelodeon,

All I want is 11-U, and music, music, music.

We could make a little diagram of what happens one evening (Fig. 86).

FIGURE 86. A self-reproducing song.

Although the effect is that the song reproduces itself, it would feel strange to call the song a self-rep, because of the fact that when it passes through the 11-U stage, not all of the information is there. The information only gets put back by virtue of the fact that it is fully stored in the nickelodeon that is, in one of the arrows in the diagram, not in one of the ovals.

It is questionable whether this song contains a complete description of how to get itself played again, because the symbol pair "1 1-U" is only a trigger, not a copy.

A "Crab" Program

Consider next a computer program which prints itself out backwards. (Some readers might enjoy thinking about how to write such a program in

the blooP-like language above, using the given sell-rep as a inouel.) vvouiu this funny program count as a self-rep. Yes, in a way, because a trivial transformation performed on its output will restore the original program. It seems fair to say that the output contains the same information as the program itself, just recast in a simple way. Yet it is clear that someone might look at the output and not recognize it as a program printed backwards. To recall terminology from Chapter VI, we could say that the "inner messages" of the output and the program itself are the same, but they have different "outer messages"-that -is, they must be read by using different decoding mechanisms. Now if one counts the outer message as part of the information-which seems quite reasonable-then the total information is not the same after all, so the program can't be counted as a self-rep.

However, this is a disquieting conclusion, because we are accustomed to considering something and its mirror image as containing the same information. But recall that in Chapter VI, we made the concept of "intrinsic meaning" dependent on a hypothesized universal notion of intelligence. The idea was that, in determining the intrinsic meaning of an object, we could disregard some types of outer message-those which would be universally understood. That is, if the decoding mechanism seems fundamental enough, in some still ill-defined sense, then the inner message which it lets be revealed is the only meaning that counts. In this example, it seems reasonably safe to guess that a "standard intelligence" would consider two mirror images to contain the same information as each other; that is, it would consider the isomorphism between the two to be so trivial as to be ignorable. And thus our intuition that the program is in some sense a fair self-rep, is allowed to stand.

Epimenides Straddles the Channel

Now another far-fetched example of a self-rep would be a program which prints itself our, but translated into a different computer language. One might liken this to the following curious version of the Quine version of the Epimenides self-ref:

'lest une expression qui, quand elle est precedee de sa traduction, mise entre guillemets, clans la langue provenant de l'autre tote de la Manche. tree une faussete"

is an expression which, when it is preceded by its translation, placed in quotation marks, into the language originating on the other side of the Channel, yields a falsehood.

You might try to write down the sentence which is described by this weird concoction. (Hint: It is not itself-or at least it is not if "itself" is taken in a naive sense.) If the notion of "self-rep by retrograde motion" (i.e., a program which writes itself out backwards) is reminiscent of a crab canon, the notion of "self-rep by translation" is no less reminiscent of "a canon which involves a transposition of the theme into another key.

A Program That Prints Out Its Own Godel Number

The idea of printing out a translation instead of an exact copy of the original program may seem pointless. However, if you wanted to write a self-rep program in BlooP or FlooP, you would have to resort to some such device, for in those languages,
OUTPUT
is always a number, rather than a typographical string. Therefore, you would have to make the program print out its own Godel number: a very huge integer whose decimal expansion codes for the program, character by character, by using three digit codons. The program is coming as close as it can to printing itself, within the means available to it: it prints out a copy of itself in another "space", and it is easy to switch back and forth between the space of integers and the space of strings. Thus, the value of
OUTPUT
is not a mere trigger, like "11-12". Instead, all the information of the original program lies "close to the surface" of the output.

Godelian Self-Reference

This comes very close to describing the mechanism of Godel's self-ref G. After all, that string of TNT contains a description not of itself, but of an integer (the arithmoquinification of u). It just so happens that that integer is an exact "image" of the string G, in the space of natural numbers. Thus, G refers to a translation of itself into another space. We still feel comfortable in calling G a self-referential string, because the isomorphism between the two spaces is so tight that we can consider them to be identical.

This isomorphism that mirrors TNT inside the abstract realm of natural numbers can be likened to the quasi-isomorphism that mirrors the real world inside our brains, by means of symbols. The symbols play quasi-isomorphic roles to the objects, and it is thanks to them that we can think. Likewise, the Godel numbers play isomorphic roles to strings, and it is thanks to them that we can find metamathematical meanings in statements about natural numbers. The amazing, nearly magical, thing about G is that it manages to achieve selfreference despite the fact that the language in which it is written, TNT, seems to offer no hope of referring to its own structures, unlike English, in which it is the easiest thing in the world to discuss the English language.