A self-writing replicating program is one which outputs itself, starting with all registers empty.

At first blush it seems paradoxical that such programs would exist: there is no direct way to get the 1# interpreter to spit out the program that is inside it. And anyways, it would seem that typically, a program is usually longer than its output. So how can a program output itself? This lesson shows how it is done. Even more, it will show you how such programs work and give you a chance to try your hand at writing related programs.

In order to get a program which writes itself, one must use some sort of trick or clever idea. Our goal is to explain one such clever idea, and then to see other applications of it as we go. Before you understand it, the idea will seem to be a trick, or even a fluke: we have a program, and it just so happens to output itself. But as we come to understand it better, the trick becomes tamed into a general method.

At the root of our work is something we've seen in the last lesson: the ability of 1# programs to write and modify other programs.

The exercises in ths lesson are much more challenging than the previous ones.

We begin with a program which we'll call diag in this lesson and in the following ones, too. When diag is run with a word x in R1, the result is φ_write(x) + x in R1. And running that gives φ_x(x) in R1.

At the bottom we have two sub-programs which we list as if they were single steps. These are move_3,1 and move_2,1 from Lesson One.

The three branches of the case instruction at the top take us to move_3,1 (if R1 is empty), to the blue sub-program if the first symbol of R1 is a 1, and to the brown sub-program if that symbol is a #. Note that we have a big loop that takes symbols off of R1 and writes the same thing in R2 and some related words in R3. The way that the words in R3 are related to the original input in R1 is as follows: each time a 1 is removed from R1, what goes into R3 is the program which would write a 1 in R1 (this is 1#). And each time a # is removed from R1, what goes into R3 is the program which would write a # in R1 (this is 1##).

It might help to say things a bit differently on this. So here is an informal description of what diag is doing:

Move x from R1 into R2, and also put φ_write(x) in R3.

Move R3 back to the now-empty R1.

Finally, move R2 onto the end of R1.

The official version of diag is a very slightly shortened version of this. You will want to copy it to the interpreter both now and in later lessons:

The tables below show the important feature of diag. You should memorize them as soon as possible for use below and in the next lesson. R1 at the start x after diag φdiag(x) = φwrite(x) +x R1 at the start after φdiag(x) φx(x) Here are these features explained in words: When diag is run with a word x in R1, the result is φwrite(x) + x in R1. This word φwrite(x) + x is the same as φdiag(x). And running that program φdiag(x) with all registers empty gives the same thing in R1 as running x on x itself. Another name for this is φx(x).

Exercise 1 What word w to we get when diag is run on 1#? What happens if w is run with R1 empty?

We now define our self-writing program, self.

The idea is to apply the program diag to diag itself.
This might seem like a strange thing to do. But as we'll see, it gives us exactly what we're looking for.

When we run diag on itself, we get φ_write(diag) + diag in R1.
This, then, is self: the program which would write out diag) followed by diag) itself.

So when we run self on nothing, we first spell out diag into R1.
After this, we run diag. But we aren't running it on empty registers, because at this point R1 contains diag.

But running diag on diag gives us self, as desired.

To summarize: running self on nothing is the same as running diag on itself; and this is self. In symbols, That is,

Here is self

The run of self takes 14,204 steps.

The idea in English

It might be useful to expose the device behind our self-replicating program self by rendering it into English.

(But the discussion here is not really needed for the formal work, and you may skip this section if you like.)

We are interested in "programs" of English (that is, sequences of instructions). We want instructions of a very simple form, including instructions to print various characters, and instructions which accept one or more sequences of words as arguments, and so on.

We'll allow a small amount of quotation.

Perhaps the most direct example of a self-replicating program would be print me.

But this is hard to adapt directly into 1#. Instead, we want to use

Here "what you see" and "it" refer to the input, and "before" means "to the left of".

Applying this English program to the English program print me would give

Let's apply this English version of diag to itself.

We get the longer program below. It is the English version of self.

Let's then see what happens if we execute that last long program. We would print out the instructions to print our version of diag, followed up by that very program.

The upshot is that we get the long program back!

And this same explanation applies to the 1# diag that we've already seen.

Another presentation of the idea

We offer another presentation of the idea behind diag and self.

Let's suppose that you want to write a self-replicating program, say s, from scratch.

Let's say that you just have on glimmer of an idea, that s should be of the following form:

1. First, a program x should be written to R1.

2. Second, a program y should be run (with x in R1 and everything else empty).

So running x on nothing will give &phi_xy in R1 at the end.

We therefore want to find s, x, and y so that

We are free to find any s, x, and y that we like that meets these requirements. Wouldn't it be nice if x = y? So why don't we just try to find s and x so that

Now it is clear that if we find x we then can determine s automatically, using the first equation. We only need to have x be a program with the property that

But again, we are free to make x be any program we like. We might as well make x have the property that for all z,

since if we do this, then it automatically will hold that φ_x(x) = φ_write(x) + x.

And now things are much easier. It is not hard to write x so that φ_x(z) = φ_write(z) + z for all z; this is diag.

Finally, the reasoning we did in this small discussion shows that we can get a self replicating program by setting s = φ_x(x).

The rest of this lesson consists of exercises that allow you to firm up your understanding of the basic ideas in diag and self by elaborating on and extending them.

In all of these exercises, you are invited to check your work on the interpreter.

Exercise 2 Write a program which when started on all empty registers writes itself to R1 and also writes # to R2.

Exercise 3 Write a program p which when started on all empty registers doesn't write itself to R1 but rather writes itself followed by a #. In other words, φp( ) = p + #

Exercise 4 Write an infinite list of programs p1, p2, . . ., pn, . . . which are all different, and such that each program in the list writes the next one in the list into R1.

Exercise 5 Write a program p which when started on all empty registers doesn't write itself to R1 but rather writes itself preceded by a #. In other words, φp( ) = # + p [Hint: modify diag.]

Exercise 6 Write a self-replicating program that begins with the program to transfer ahead one instruction, 1###.

Exercise 7 Which programs p have the property that there is a self-replicating program which begins with p?

Exercise 8 Write a program s which, when run with R2, R3, etc. empty, ends up with R1 containing s after whatever happened to be in R1 at the start. In other words, for all words y, φs(y) = y + s

Exercise 9 Write a program selfknow with the property that when run with a string q in R1, selfknow runs and halts with q in R1 if q= selfknow, and runs and halts with # in R1 empty if q is not equal to selfknow. (So this program selfknow "knows itself".)

Exercise 10 Write a program trade which trades places with its input in R1. That is, running trade with p in R1 and all other registers empty does the same thing as running p with trade in R1 and all other registers empty. [You will probably want to work through Lesson Six before attempting this problem. But it might be fun to try now.]

Exercise 11 Write two "twin'' programs s and t with the properties that s and t are different programs; running s with all registers empty gives t in R1; running t with all registers empty gives s in R1.

This section has yet to be written.