Self-writing programs

Self-writing programs#

Attention

Note for instructors

Technically, this section is not necessary in order to prove the Recursion Theorem in the next section. One could immediately go there. But I feel that most people would find this section more approachable, and so I recommend using it. If one does omit this section, the exercises here still could be worked based on the Recursion Theorem.

A self-writing 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 \(\onesharp\) interpreter to spit out the program that is inside it. 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 from early on, the ability of \(\onesharp\) 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,

\[ [\![ [\![ {\tt diag} ]\!](x)]\!](\ ) \simeq [\![ x ]\!](x) \]

We have already seen such a program: copy_1_3_2 + write + move_3_1 See Exercise 40. 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 move_3,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)
move_3,1	from earlier
move_2,1	from earlier

The three branches of the case instruction at the top take us to \(\moveprog_{3,1}\) (if R1 is empty), to the blue sub-program if the first symbol of R1 is a \(\onett\), and to the brown sub-program if that symbol is a \(\hash\). 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 \(\onett\) is removed from R1, what goes into R3 is the program which would write a \(\onett\) in R1 (this is \(\onesharp\)). And each time a \(\hash\) is removed from R1, what goes into R3 is the program which would write a \(\hash\) in R1 (this is \(\onett\hash\hash\)).

Important

We often will use the following facts:

\[\begin{split} \begin{array}{rcl} \semantics{\diagprog}(x) & \simeq & \semantics{\writeprog}(x) + x \\ \semantics{\semantics{\diagprog}(x)}(y)& \simeq & \semantics{x}(y+x) \end{array} \end{split}\]

Also our program \({\tt diag}\) uses only R1, R2, and R3.

Self#

We now define a self-writing program, \(\selfprog\). The idea is to apply the program \(\diagprog\) to \(\diagprog\) 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 \(\diagprog\) on itself, we get \(\semantics{\writeprog}(\diagprog) + \diagprog\) in R1. This, then, is \(\selfprog\). When we run \(\selfprog\) on nothing, we first write \(\diagprog\) into R1. After this, we run \(\diagprog\). At the point we are running \(\diagprog\), R1 contains \(\diagprog\), and the other registers are empty. So we get \(\selfprog\), by definition.

To summarize: running \(\selfprog\) on nothing is the same as running \(\diagprog\) on \(\diagprog\) itself; and this is \(\selfprog\).

Summary

\( [\![\self]\!] (\ ) = [\![ [\![\diag]\!](\diag)]\!]( ) = [\![\diag]\!](\diag) \simeq \self \).

Here is \(\selfprog\). You can watch the calculation by copying the program below and pasting it into the program editor box of the Javascript interpreter for 1#. Be sure to use eval slow.

1#1##1##1##1##1##1#1#1#1#1#1#1#1#1#1#1#1##1##1##1#1#1#1#1#1#1##1##1##1#1#1##1##1#1#1#1##1#1#1#1##1##1#1#1#1##1##1#1#1#1#1#1#1#1##1##1##1##1#1#1##1#1#1#1##1#1#1#1##1##1#1#1#1#1##1##1##1##1#1#1#1##1##1##1##1##1#1#1#1#1#1#1##1##1##1#1#1#1##1##1##1#1##1##1#1#1#1#1##1##1##1##1#1##1#1#1##1##1##1##1#1#1##1##1##1##1##1#1#1#1#1#1#1##1##1##1#1#1#1##1##1##1#1##1##1#1#1#1#1##1##1##1##1#1##1#1#1##1##1##1##1#####11111111111###111111###11##111#111##111##1111111####11#111#111##1111####111#####111111###111###1##1111####1#11####11#####111111###111###1##1111####1#11####

You can also do some calculations if you run programs on Colab or CoCalc.

onesharp(self,[])

onesharp(self,[])== self

The idea in words#

We present one idea that could explain what is behind \(\diagprog\) and \(\selfprog\). Let’s suppose that you want to write a self-replicating program, say \(s\), from scratch. Let’s say that you just have a glimmer of an idea: a self-replicating program \(s\) should be a two-stage affair; when we run \(s\) on empty registers, we first write a word \(x\) to R1, and then run some program \(y\) on \(x\). And of course, we want the result of running \(y\) on \(x\) to be \(s\). So in effect, we want to solve a system of equations:

\[\begin{equation*} \begin{array}{lcl} s & = & \semantics{\writeprog} (x)+ y \\ \semantics{s}(\ ) & = & s\\ \end{array} \label{eq:systemstart}\tag{1} \end{equation*}\]

But these give

\[\begin{equation*} \label{eq:deriveK2}\tag{2} \semantics{y}(x) = \semantics{s}(\ ) = s = \semantics{\writeprog} (x)+ y \end{equation*}\]

We are free to find any \(x\) and \(y\) that we like that satisfies \(\eqref{eq:deriveK2}\), since then we could take solve the original system by taking \(s\) to be \([\![ \writeprog]\!](x)+ y\).

Now here is where things become interesting. Instead of simply finding any old \(x\) and \(y\) satisfying \(\eqref{eq:deriveK2}\), let’s find some \(y\) such that for all \(x\), we have the following different condition:

\[\begin{equation*} \label{eq:deriveK2trick}\tag{3} \semantics{y}(x) = \semantics{\writeprog} (x)+ x \end{equation*}\]

(Note that \(\eqref{eq:deriveK2}\) and \(\eqref{eq:deriveK2trick}\) are different due to the last symbol in each.) If we find \(y\) to make \(\eqref{eq:deriveK2trick}\) hold for all \(x\), we can set \(x = y\); this arranges \(\eqref{eq:deriveK2}\).

It looks like we made our problem harder by asking \(y\) to satisfy a more stringent condition. But in reality it’s easier, since \(\eqref{eq:deriveK2trick}\) only has \(y\) on one side. So it is much more manageable. In fact, we can solve it by simply taking \(y\) to be \(\diagprog\)!

To conclude: we take \(y = \diagprog\) and \(x = y\). This arranges that all of our equations hold.
We thus can get a self replicating program by setting \(s = [\![ \writeprog]\!](\diagprog)+ \diagprog = [\![ \diagprog]\!](\diagprog)\).

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 73

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

Exercise 74

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 75

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 76

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 77

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

Exercise 78

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 79

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 80

A country adopts 1# as its national programming language. To celebrate, they want a new flag. Write a program flag with the property that running flag on all empty registers gives two copies of flagseparated by a stripe with the same number of characters as flag. The stripe should have all # symbols.