Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

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 ll-U, will playa 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).

person

nickelodeon

FIGURE 86. A selj~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 "11-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

500 Self-Ref and Self-Rep