{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "\"Open" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "mjtzV10cAMR5" }, "source": [ "# Self-writing programs\n", "\n", "A self-writing replicating program is one which outputs itself, starting with all registers empty.\n", "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.\n", "\n", "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.\n", "\n", "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.\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "WKstbnoBDdMN" }, "outputs": [], "source": [ "!python -m pip install -U setuptools\n", "!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main\n", "from onesharp.interpreter.interpreter import *" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ibYhzz7UCQYa" }, "source": [ "# Diag\n", "\n", "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: \n", "$[\\![x]\\!](x)$. \n", "\n", "Thus, \n", "\n", "$$\n", "[\\![ [\\![ {\\tt diag} ]\\!](x)]\\!](\\ ) \\simeq [\\![ x ]\\!](x)\n", "$$\n", "\n", "We have already seen such a program: ```copy_1_3_2 + write + move_3_1``` See {ref}`pre-diag`. However, we want a slightly different program, only because it is a little shorter.\n", "\n", "We take ```diag``` to be the program shown below." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "

\n", "

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
1##### Cases on R1
11111111111### Go forward 11:\n", " to move3,1 part
111111###Go forward 6:\n", "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\n", "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\n", "(to the top)
move3,1 from Lesson 1
move2,1 from Lesson 1
\n", "
\n", "

" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "mKfRQC6XAiGV" }, "source": [ "\n", "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##```).\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{admonition} Important\n", ":class: tip\n", "\n", "We often will use the following fact:\n", "\n", "$$\n", "[\\![ [\\![ {\\tt diag} ]\\!](x)]\\!](y) \\simeq [\\![ x ]\\!](y+x).\n", "$$\n", "\n", "Also our program ${\\tt diag}$ uses only R1, R2, and R3.\n", "```\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "jt4sdyWxAh2c" }, "source": [ "" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "0FIHwdHrAhmr" }, "source": [ "# Self\n", "\n", "We now define a self-writing program, ```self```.\n", "\n", "The idea is to apply the program ```diag``` to diag itself.\n", "This might seem like a strange thing to do. But as we'll see, it gives us exactly what we're looking for.\n", "When we run ```diag``` on itself, we get ```[[ write]](diag) + diag``` in R1.\n", "This, then, is ```self```: the program which would write out the word ```diag``` into R1 followed by an application of\n", "the program ```diag```.\n", "\n", "So when we run ```self``` on nothing, we first spell out diag into R1.\n", "After this, we run ```diag```. Notice that we aren't running ```diag``` on empty registers, because at this point R1 contains ```diag```.\n", "But running ```diag``` on ```diag``` gives us ```self```, by definition.\n", "\n", "So we conclude that running ```self``` on nothing gives ```self```, as desired.\n", "\n", "To summarize: running ```self``` on nothing is the same as running ```diag``` on ```diag``` itself; and this is ```self```. In symbols:\n", "\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ClEUijpf-lxx" }, "source": [ "```{admonition} Summary\n", ":class: tip\n", "\n", "$\n", "[\\![self]\\!] (\\ ) = [\\![ [\\![ diag]\\!](diag)]\\!]( ) = [\\![ diag]\\!](diag) \\simeq self\n", "$.\n", "```\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "You can watch the calculation by entering ```self``` in the Javascript interpreter for ```1#```." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 107 }, "id": "WxlKvm0P_xl4", "outputId": "79fc1b44-7ade-4cef-f7df-63b00b583ee6" }, "outputs": [], "source": [ "self" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "88La6m9mKYKo" }, "outputs": [], "source": [ "onesharp(self,[])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "0RYaVkTvKcCi" }, "outputs": [], "source": [ "onesharp(self,[])== self" ] }, { "cell_type": "markdown", "metadata": { "id": "5Nfr-OzHEwRj" }, "source": [ "The run of ```self``` on empty registers takes 14,204 steps to output itself." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "OE0t7FYBF9f4" }, "source": [ "### The idea in English\n", "\n", "We offer another presentation of the idea behind diag and self.\n", "\n", "Let's suppose that you want to write a self-replicating program, say $s$, from scratch.\n", "\n", "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$.\n", "So in effect, we want to solve a *system of equations*\n", "\n", "$$\n", "\\begin{array}{lcl}\n", "s & = & [\\![ write]\\!](x)+ y\\\\\n", "[\\![ s]\\!](\\ ) & = & [\\![ y]\\!](x)\\\\\n", "[\\![ [\\![ y]\\!](x) ]\\!](\\ ) & = & s \\\\\n", "\\end{array}\n", "$$\n", "\n", "The second of these follows from the first, of course. Putting together the first and third gives\n", "\n", "$$\n", "\\begin{array}{lcl}\n", "[\\![ [\\![ y]\\!](x) ]\\!](\\ ) & = & [\\![ write]\\!](x)+ y \\quad (*)\\\\\n", "\\end{array}\n", "$$\n", "\n", "\n", "\n", "We are free to find any $x$, and $y$ that we like that satisfies (*), since then we \n", "could take $s$ to be $[\\![ write]\\!](x)+ y$. \n", "\n", "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:\n", "\n", "$$\n", "[\\![ [\\![ y]\\!](x) ]\\!](\\ ) = [\\![ write]\\!](x)+ x, \\quad (**)\n", "$$\n", "and then set $x = y$.\n", "(Note that (*) and (**) are different due to the last symbol in each.)\n", "\n", "If we find $y$ to make (**) hold for all $x$, we can set $x = y$ and thus have (*), because\n", "\n", "$$\n", "[\\![ [\\![ y]\\!](x) ]\\!](\\ ) = [\\![ write]\\!](x)+ x = [\\![ write]\\!](x)+ y\n", "$$\n", "\n", "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$!\n", "\n", "To conclude: we take $y = diag$ and $x = y$. This arranges that all of our equations hold. \n", "We thus can get a self replicating program by setting $s = [\\![ write]\\!](diag)+ diag = [\\![ diag]\\!](diag)$." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "6tEUYD1mGnO_" }, "source": [ "" ] }, { "cell_type": "markdown", "metadata": { "id": "wima6HB4GkrE" }, "source": [ "# Exercises\n", "\n", "\n", "The rest of this lesson consists of exercises that allow\n", "you to firm up your understanding of the basic ideas\n", "in ```diag``` and ```self``` by elaborating on \n", "and extending them.\n", "\n", "In all of these exercises, you are invited\n", "to check your work on the interpreter." ] }, { "cell_type": "markdown", "metadata": { "id": "J_-lyQ1o1A48" }, "source": [ "```{exercise}\n", "If x and y are words, let's think about \n", "[ [```diag```] (```x```)] (```y```). Is it [[ ```x``` ]](```x + y```), or \n", " [[ ```x``` ]](```y + x```)?\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "25PpJ0syINFo" }, "source": [ "```{exercise}\n", "Write a program which when started on all empty registers\n", "writes itself to R1 and also writes ```#``` to R2.\n", "```\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "FY4buiFkINAl" }, "source": [ "```{exercise}\n", "Write a program $p$ which when started on all empty registers\n", "doesn't \n", "write itself to R1 but rather writes itself followed by a ```#```.\n", "In other words, $[\\![ p]\\!](\\ ) = p + \\# $.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "GiEhOwzUIM8g" }, "source": [ "```{exercise}\n", "Find an infinite sequence of programs which are all different with the property that each program in the list\n", "writes the next one in the list into R1.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ZZI9Q27WIM4O" }, "source": [ "```{exercise}\n", "Write a program $p$ which when started on all empty registers\n", "doesn't \n", "write itself to R1 but rather writes itself preceded by a ```#```.\n", "In other words, $[\\![ p]\\!](\\ ) = \\# +p$.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "O-FicJXVIM1I" }, "source": [ "```{exercise}\n", "Write a self-replicating program \n", "that begins with the program to transfer ahead\n", "one instruction, ```1###```.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "P_ZjX7IbIMxg" }, "source": [ "```{exercise}\n", "Write a program $s$ which, when run with R2, R3, etc.\n", "empty, ends up with R1 containing $s$ *after* whatever\n", "happened to be in R1 at the start.\n", "In other words, for all words $y$, $[\\![ s]\\!](y) = y+s$.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "ZOVvoh-4IMuO" }, "source": [ "```{exercise}\n", "Write a program ```selfknow``` with the property that when run with\n", "a string q in R1, \n", "```selfknow``` runs and halts with q in R1 if q=\n", "```selfknow```, and runs and halts with ```#``` in R1 empty if q is not \n", "equal to ```selfknow```.\n", "(So this program ```selfknow``` \"knows itself\".)\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "EFzMsYZWIMqz" }, "source": [ "```{exercise} \n", "Write a program ```trade```\n", "which trades places with its input in R1.\n", "That is, running ```trade``` with p in R1\n", "and all other registers empty does the same thing\n", "as running p with ```trade``` in R1 and all other\n", "registers empty.\n", "\n", "[You will probably want to work through some later lessons\n", "before attempting this problem. But it might be fun to try now.] \n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "iOBfuEL-IMiv" }, "source": [ "```{exercise}\n", "Write two \"twin'' programs $s$ and $t$ with the properties\n", "that $s$ and $t$ are different programs;\n", "running $s$ with all registers empty gives $t$ in R1; and \n", "running $t$ with all registers empty gives $s$ in\n", "R1.\n", "\n", "\"Different\" here means that $s$ and $t$ are not symbol-for-symbol the same.\n", "```" ] } ], "metadata": { "colab": { "authorship_tag": "ABX9TyOUskvjlC52E7pXPt0B/94t", "include_colab_link": true, "provenance": [] }, "kernelspec": { "display_name": "Python 3", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.2" } }, "nbformat": 4, "nbformat_minor": 0 }