{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [], "authorship_tag": "ABX9TyOUskvjlC52E7pXPt0B/94t", "include_colab_link": true }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "view-in-github", "colab_type": "text" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "source": [ "# Self-Replicating 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" ], "metadata": { "id": "mjtzV10cAMR5" } }, { "cell_type": "code", "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 *" ], "metadata": { "id": "WKstbnoBDdMN" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "" ], "metadata": { "id": "css7-S_FAiQl" } }, { "cell_type": "markdown", "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 \n", "\n", "$\\semantics{\\writeprog}(x) + x$\n", "\n", "\n", "\n", "Running that last program on all empty registers gives the same thing as running x on itself:\n", "\n", "$\\semantics{x}(x)$\n", "\n", "in R1, assuming that\n", "$\\semantics{x}(x)$\n", " is defined.\n", "\n", "\n" ], "metadata": { "id": "ibYhzz7UCQYa" } }, { "cell_type": "markdown", "source": [ "Here is the program ```diag```:" ], "metadata": { "id": "vraQPSVMjBro" } }, { "cell_type": "code", "source": [ "#@title\n", "j = [['1#####', 'cases on R1', 0],\n", " ['11111111111###', 'go forward 11 to instruction 13 (the start of move_3_1)', 1],\n", " ['111111###', 'go forward 6 to instruction 9 (the tan part)', 2],\n", " ['11##', 'R1 started with #: add # to R2', 3],\n", " ['111#', 'add 1 to R3', 4],\n", " ['111##', 'add # to R3', 5],\n", " ['111##', 'add # to R3', 6],\n", " ['1111111####', 'go backward 7 to instruction 1', 7],\n", " ['11#', 'R1 started with 1: add 1 to R2', 8],\n", " ['111#', 'add 1 to R3', 9],\n", " ['111##', 'add # to R3', 10],\n", " ['1111####', 'go backward 4 to instruction 8', 11],\n", " ['111#####', 'move_3_1 (from the first lesson)', 12],\n", " ['111#####', 'move_2_1 (from the first lesson)', 13]\n", " ]\n", "\n", " \n", "df = pd.DataFrame(j,columns=[\"instruction\", 'explanation','number'])\n", "df.index = np.arange(1, len(df) + 1)\n", "df.style.set_properties(**{'border': '1.3px solid green',\n", " 'color': 'magenta'})\n", "n = len(df.columns)\n", "df.style.set_properties(**{'text-align': 'left'})\n", "df.drop('number', axis=1) # !!! we want this!\n", "#df.style.apply(lambda x: [\"background-color: red\"]*n if x['instruction']== 'Reading' else [\"background-color: white\"]*n, axis = 1)\n", "#df.style.apply(lambda x: [\"background-color: #B0E0E6\"]*n if x['instruction'] in ['1##','1111####'] elif [\"background-color: #D4B48C\"]*n if x['instruction'] in ['1#','111111####'] else [\"background-color: #FFFFCC\"]*n, axis = 1)\n", "df.style.apply(lambda x: [\"background-color: #B0E0E6\"]*n if x['instruction'] in ['1##','1111####'] else [\"background-color: #FFFFCC\"]*n, axis = 1)\n", "\n", "df.style.hide_columns('number')\n", "df.style.apply(lambda x: \n", " [\"background-color: #B0E0E6\"]*n if x['number'] in [3,4,5,6,7] \n", " else [\"background-color: tan\"]*n if x['number'] in [8,9,10,11]\n", " else [\"background-color: #FFFFCC\"]*n, axis = 1)\n", "\n" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 488 }, "cellView": "form", "id": "uwrhfAGyNpzV", "outputId": "a86ac42a-d3b6-466f-a8c9-740af4a9147b" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "" ], "text/html": [ "\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", " \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", " \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", "
 instructionexplanationnumber
11#####cases on R10
211111111111###go forward 11 to instruction 13 (the start of move_3_1)1
3111111###go forward 6 to instruction 9 (the tan part)2
411##R1 started with #: add # to R23
5111#add 1 to R34
6111##add # to R35
7111##add # to R36
81111111####go backward 7 to instruction 17
911#R1 started with 1: add 1 to R28
10111#add 1 to R39
11111##add # to R310
121111####go backward 4 to instruction 811
13111#####move_3_1 (from the first lesson)12
14111#####move_2_1 (from the first lesson)13
\n" ] }, "metadata": {}, "execution_count": 53 } ] }, { "cell_type": "markdown", "source": [ "\n", "The three branches of the case instruction at the top take us to move3,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", "\n", "It might help to say things a bit differently on this. So here is an informal description of what diag is doing:\n", "Move x from R1 into R2, and also put $\\semantics{\\writeprog}(x)$ in R3.\n", "Then \n", "move R3 back to the now-empty R1.\n", "Finally, move R2 onto the end of R1.\n", "The official version of ```diag``` is a very slightly shortened version of this. \n", "\n", "The tables below show the important feature of ```diag```. You should memorize it as soon as possible for use below and in the next lesson.\n", "\n", "Running ```diag``` on a word ```x``` and then running that on the empty register yields the same thing as running ```x``` on iself.\n" ], "metadata": { "id": "mKfRQC6XAiGV" } }, { "cell_type": "markdown", "source": [ "" ], "metadata": { "id": "jt4sdyWxAh2c" } }, { "cell_type": "markdown", "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 $\\phifn_{\\writeprog}(\\diag) + \\diag$ in R1.\n", "This, then, is $\\self$: the program which would write out ```diag``` followed by ```diag``` itself.\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" ], "metadata": { "id": "0FIHwdHrAhmr" } }, { "cell_type": "markdown", "source": [ "````{admonition} Summary\n", ":class: tip\n", "\n", "$\n", "\\semantics{\\self}(\\ ) = \\semantics{\\diag}{\\diag) \\simeq \\self\n", "$.\n", "````\n", "\n" ], "metadata": { "id": "ClEUijpf-lxx" } }, { "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": [ { "output_type": "execute_result", "data": { "text/plain": [ "'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####'" ], "application/vnd.google.colaboratory.intrinsic+json": { "type": "string" } }, "metadata": {}, "execution_count": 10 } ], "source": [ "self" ] }, { "cell_type": "code", "source": [ "onesharp(self,[])" ], "metadata": { "id": "88La6m9mKYKo" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "onesharp(self,[])== self" ], "metadata": { "id": "0RYaVkTvKcCi" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "The run of ```self``` on empty registers takes 14,204 steps to output itself." ], "metadata": { "id": "5Nfr-OzHEwRj" } }, { "cell_type": "markdown", "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 s should be of the following form:\n", "\n", "First, a program x should be written to R1.\n", "\n", "Second, a program y should be run (with x in R1 and everything else empty).\n", "\n", "So running x on nothing will give &phixy in R1 at the end.\n", "\n", "We therefore want to find s, x, and y so that\n", "\n", "s= φwrite(x) + y, φs( ) = φx(y )\n", "and\n", "φx(y) = s\n", "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\n", "\n", "s= φwrite(x) + x,\n", "and also\n", "φx(x) = s\n", "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\n", "\n", "φx(x) = φwrite(x) + x,\n", "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,\n", "\n", "φx(z) = φwrite(z) + z,\n", "since if we do this, then it automatically will hold that φx(x) = φwrite(x) + x.\n", "\n", "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.\n", "Finally, the reasoning we did in this small discussion shows that we can get a self replicating program by setting s = φx(x)." ], "metadata": { "id": "OE0t7FYBF9f4" } }, { "cell_type": "markdown", "source": [ "" ], "metadata": { "id": "6tEUYD1mGnO_" } }, { "cell_type": "markdown", "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." ], "metadata": { "id": "wima6HB4GkrE" } }, { "cell_type": "markdown", "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", "```" ], "metadata": { "id": "J_-lyQ1o1A48" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a program which when started on all empty registers\n", "writes itself to $\\Rone$ and also writes $\\hash$ to $\\Rtwo$.\n", "```\n" ], "metadata": { "id": "25PpJ0syINFo" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a program $p$ which when started on all empty registers\n", "doesn't \n", "write itself to $\\Rone$ but rather writes itself followed by a $\\hash$.\n", "In other words, $\\phifn_p(\\ ) = p + \\hash$.\n", "```" ], "metadata": { "id": "FY4buiFkINAl" } }, { "cell_type": "markdown", "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", "```" ], "metadata": { "id": "GiEhOwzUIM8g" } }, { "cell_type": "markdown", "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,\n", "$\\phifn_p(\\ ) = \\# + p$.\n", "```" ], "metadata": { "id": "ZZI9Q27WIM4O" } }, { "cell_type": "markdown", "source": [ "```{exercise}\n", "Write a self-replicating program \n", "that begins with the program to transfer ahead\n", "one instruction, ```1###```.\n", "```" ], "metadata": { "id": "O-FicJXVIM1I" } }, { "cell_type": "markdown", "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,\n", "$\\phifn_s(y) = y + s$\n", "```" ], "metadata": { "id": "P_ZjX7IbIMxg" } }, { "cell_type": "markdown", "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", "```" ], "metadata": { "id": "ZOVvoh-4IMuO" } }, { "cell_type": "markdown", "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", "```" ], "metadata": { "id": "EFzMsYZWIMqz" } }, { "cell_type": "markdown", "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", "```" ], "metadata": { "id": "iOBfuEL-IMiv" } } ] }