Self-writing programs#
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.
!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *
Diag#
We begin with a program which we’ll call diag. When diag is run with a word \(x\) in R1, the result is \([\![ {\tt write} ]\!](x) + x\). Then, running that last program on all empty registers gives the same thing as running x on itself:
\([\![x]\!](x)\).
Thus,
We have already seen such a program: copy_1_3_2 + write + move_3_1 See Exercise 26. However, we want a slightly different program, only because it is a little shorter.
We take diag to be the program shown below.
| 1##### | Cases on R1 |
| 11111111111### | Go forward 11: to move3,1 part |
| 111111### | Go forward 6: to the brown part |
| 11## | Add # to R2 |
| 111# | Add 1 to R3: 1## adds # to R1 |
| 111## | Add # to R3 |
| 111## | Add # to R3 |
| 1111111#### | Go backward 7 (to the top) |
| 11# | Add 1 to R2 |
| 111# | Add 1 to R3: 1# adds 1 to R1 |
| 111## | Add # to R3 |
| 11111111111#### | Go backward 11 (to the top) |
| move3,1 | from Lesson 1 |
| move2,1 | from Lesson 1 |
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##).
Important
We often will use the following fact:
Also our program \({\tt diag}\) uses only R1, R2, and R3.
Self#
We now define a 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 the word diag into R1 followed by an application of
the program diag.
So when we run self on nothing, we first spell out diag into R1.
After this, we run diag. Notice that we aren’t running diag on empty registers, because at this point R1 contains diag.
But running diag on diag gives us self, by definition.
So we conclude that running self on nothing gives self, as desired.
To summarize: running self on nothing is the same as running diag on diag itself; and this is self. In symbols:
Summary
\( [\![self]\!] (\ ) = [\![ [\![ diag]\!](diag)]\!]( ) = [\![ diag]\!](diag) \simeq self \).
You can watch the calculation by entering self in the Javascript interpreter for 1#.
self
onesharp(self,[])
onesharp(self,[])== self
The run of self on empty registers takes 14,204 steps to output itself.
The idea in English#
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 when we run \(s\) on empty registers, we first write a word \(x\) to R1, and then run a program \(y\) on it. And of course, we want the result of running \(y\) on \(x\) should be \(s\). So in effect, we want to solve a system of equations
The second of these follows from the first, of course. Putting together the first and third gives
We are free to find any \(x\), and \(y\) that we like that satisfies (*), since then we could take \(s\) to be \([\![ write]\!](x)+ y\).
Now here is where things become interesting. Instead of simply finding any old \(x\) and \(y\) satisfying the last equation, let’s find some \(y\) such that for all \(x\), we have the following different condition:
and then set \(x = y\). (Note that (*) and (**) are different due to the last symbol in each.)
If we find \(y\) to make (**) hold for all \(x\), we can set \(x = y\) and thus have (*), because
It looks like we made our problem harder by asking \(y\) to satisfy a more stringent condition. But in reality it’s easier, since the second equation (**) only has \(y\) on one side. So it is much more manageable. In fact, we can solve it by simply taking \(y\) to be \(diag\)!
To conclude: we take \(y = diag\) and \(x = y\). This arranges that all of our equations hold.
We thus can get a self replicating program by setting \(s = [\![ write]\!](diag)+ diag = [\![ diag]\!](diag)\).
Exercises#
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 53
If x and y are words, let’s think about
[ [diag] (x)] (y). Is it [[ x ]](x + y), or
[[ x ]](y + x)?
Exercise 54
Write a program which when started on all empty registers
writes itself to R1 and also writes # to R2.
Exercise 55
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 56
Find an infinite sequence of programs which are all different with the property that each program in the list writes the next one in the list into R1.
Exercise 57
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\).
Exercise 58
Write a self-replicating program
that begins with the program to transfer ahead
one instruction, 1###.
Exercise 59
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 60
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 61
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 some later lessons before attempting this problem. But it might be fun to try now.]
Exercise 62
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; and running \(t\) with all registers empty gives \(s\) in R1.
“Different” here means that \(s\) and \(t\) are not symbol-for-symbol the same.