Complexity_ A Guided Tour - Melanie Mitchell [57]
FIGURE 8.2. A self-copying program.
In memory location 2 a variable L is set to ip−1. Recall that ip is the location of the instruction currently being executed. So when line 2 is executed, ip is set to 2 and L is set to 2 − 1 = 1. (Note that L will now stay equal to 1 until it is reset, even though ip changes as each instruction is executed.)
Next, a loop is entered, which will be iterated until line[L] is equal to the character string end. Remember that line[L] is equal to the string located in memory location L. Right now, L is set to 1, so line[L] is equal to the string program selfcopy. This is not equal to the string end, so the loop is continued. In the loop, line[L] is printed and L is incremented. First, with L = 1, program selfcopy is printed; then L is set to 2.
Now, line[L] is the second line of the program, namely L = ip - 1. Again, this string is not equal to end, so the loop is continued. In this way, each line of the program is printed out. A particularly interesting line is line 5: when line 5 is being executed with L = 5, the instruction print(line[L]) prints itself out. When L = 9 and line[L] is equal to end, the loop ends. At this point, lines 1–8 have been printed. The instruction pointer moves to line 8 (the instruction immediately following the loop), which, when executed, prints out the string “end,” completing the self-copying.
The essence of self-copying in this program is to use the same information stored in memory in two ways: first as instructions to be executed, and second as data to be used (i.e., printed) by those instructions. This dual use of information is what allows us to avoid an infinite regress of the kind illustrated earlier by my first attempt at a self-copying program.
The Deeper Meaning of the Self-Reproducing
Computer Program
The dual use of information is also at the heart of Gödel’s paradox, embodied by his self-referential sentence “This statement is not provable.”
This is a bit tricky to understand. First, let’s note that this sentence, like any other English sentence, can be looked at in two ways: (1) as the literal string of letters, spaces, and punctuation contained in the sentence, and (2) as the meaning of that literal string, as interpreted by an English speaker.
To be very clear, let’s call the literal string of characters S. That is, S = “This statement is not provable.” We can now state facts about S: for example, it contains twenty-six letters, four spaces, and one period.
Let’s call the meaning of the sentence M. We can rewrite M as follows: “Statement S is not provable.” In a way, you can think of M as a “command” and of S as the “data” for that command. The weird (and wonderful) thing is that the data S is the same thing as the command M. The chief reason Gödel was able to translate his English sentence into a paradox in mathematics was that he was able to phrase M as a mathematical statement and S as a number that encoded the string of characters of that mathematical statement.
This is all very tricky. This kind of distinction between literal strings of characters and the meaning of those strings, and the paradoxes that self-reference can produce, are discussed in a detailed and very entertaining way in Douglas Hofstadter’s book Gödel, Escher, Bach: an Eternal Golden Braid.
Similarly, this kind of dual use of information is key to Turing’s proof of the undecidability of the Halting problem. Remember H and H from chapter 4? Do you recall how H ran on its own code? That is, just like our self-reproducing computer program above, H was used in two ways: as an interpreted program and as the input for that program.
Self-Replication in DNA
At this point you may be groaning that we’re back in the abstract realm of logical headaches. But give me a minute to bring us back to reality. The really amazing thing is that this dual use of information is key to the way DNA replicates itself.