{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "\"Open" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "5ju1mn7Tur1V" }, "source": [ "# Universal programs\n", "\n", "We discuss universal programs:\n", "these are programs that take a program as an inputs and (act as if they) run\n", "the input program.\n", " \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "cellView": "form", "id": "F2axy4PUvHFm" }, "outputs": [], "source": [ "#@title\n", "!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": {}, "source": [ "```{admonition} Definition\n", ":class: attention\n", "\n", "A word $u$ is *universal* if\n", "\n", "$$\n", "[\\![u]\\!] (x) \\simeq [\\![x]\\!](\\ )\n", "$$\n", "\n", "for all words $x$.\n", "```\n", "\n", "This means that if running $x$ on all empty registers eventually gives some output in R1 (and all other registers are empty), then that same output would be the result of running $u$ with $p$ in R1 and all other registers empty. In the other direction, *if* running $x$ with all empty registers gives some output, say $y$, in R1 (and all registers empty at the end), then we would get the same output $y$ in R1 when we run $u$ with $x$ in R1 and all other registers empty.\n", "\n", "Let's take a look at such a program and try it out." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 571 }, "id": "4X9YC9eTu3M1", "outputId": "974ba216-d1b7-4ba7-d1c7-6bb04e92426a" }, "outputs": [], "source": [ "u = universal\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "TQkSinvCvOPp" }, "source": [ "```{admonition} Examples\n", "\n", "$[\\![u]\\!](\\one\\hash) \\simeq \\one$ because $[\\![\\one\\hash]\\!](\\ )\\simeq \\one$.\n", "\n", "$[\\![u]\\!](\\one)\\!\\uparrow$ because $\\one$ is not a program.\n", "```\n", "\n", "```{admonition} More examples\n", "You might try to figure out what the next two should be and then confirm your guesses by running them.\n", "\n", "$[\\![u]\\!](\\one\\hash\\one\\hash\\hash)$\n", "\n", "\n", "$[\\![u]\\!](\\one\\hash \\one\\hash\\hash \\one\\hash \\one\\hash \\hash \\one\\hash \\hash+ u)$\n", " \n", "```\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ff5wd-MKyn9C" }, "source": [ "\n", "### Let's write a universal program\n", "\n", "\n", "The next goal is for you to write a universal program\n", "yourself, either alone or with others. \n", "The next sections guide you, using a series of exercises.\n", "\n", "We hasten to make two remarks: first of all, it would be more\n", "instructive for you to forget about the rest of this lesson \n", "entirely and to just write your own universal program. But \n", " most readers would probably appreciate the hints and will find\n", "enough of a challenge in the construction of a long working program.\n", "\n", "Second, the sections to come do not guide you to write a program that\n", "is *exactly* like $u$ above. The program $u$ \n", "above was designed to be as short as possible.\n", "In fact, we leave you with a challenge: write a universal\n", "program with the smallest number of instructions. The one above has \n", "300." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "rDOKl29NwPvA" }, "source": [ "### Simplification\n", "\n", "We are going to simplify the requirements in order to make\n", "it easier to write a universal program. So we'll outline how\n", "to write a program that is close to a universal program,\n", "but not quite a universal program.\n", "\n", "We'll write a program $u$ that acts like a universal\n", "program, but *only for programs which use only R1, R2, and R3*.\n", "In more detail:\n", " \n", "Let $p$ be any\n", "program of ```1#``` which only uses R1, R2, and R3.\n", "Let $x$ be any word on our alphabet ```{1#}```,\n", "including possibly the empty word. Then the following are equivalent: \n", "\n", "(A')\n", "If $p$ is started with all empty registers, then eventually we halt\n", "with $x$ in R1. \n", "\n", "(B') If $u$ is started with $p$ in R1 and with the empty word \n", "in all other\n", "registers, then eventually we halt with $x$ in R1. \n", "\n", "Once again, the work of this section sketches a construction of \n", "such a program $u$. You will need to do much of the work yourself\n", "in actually getting the program from the sketch. And even when we\n", "have $u$, it will not be what we really want, since\n", "the resulting program $u$ will only behave right on programs which use the first\n", "three registers. \n", "Later on, we'll come\n", "back and drop this simplification to get a program which is truly \n", "universal.\n", "\n", "At this point, we are ready to sketch a method for you to\n", "write a universal program subject to this simplification.\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "We are going to use pseudo-registers as follows:\n", "\n", "
\n", "\n", " \n", " \n", "\n", " \n", " \n", " \n", " \n", "
R1: the input program p
R2: an instruction number 1n\n", "
R3: the nth instruction of p \n", "
R4: the contents of the real R1
R5: the contents of the real R2
R6: the contents of the real R3
\n", "
\n", "

\n", "That is, we are going to simulate the \n", "computation of a register machine on a program p by\n", "using six registers. Our universal program u \n", "mimics what a register machine would do.\n", "The only difference is that one step of a real register machine\n", "would be done by *many* steps of our universal program.\n", "\n", "\n", "The registers above hold what is sometimes called a snapshot\n", "of a register machine run. \n", "This means that they hold all of the relevant information about a register\n", "machine computation at one particular point in time: they tell what program is\n", "running, which instruction would be run next and what number instruction it is,\n", "and also the contents of all of the registers that the program is using.\n", "Now a real register machine goes from snapshot to snapshot in one step,\n", "but the universal machine that we are building will take many steps to\n", "go from one snapshot to the next. \n", "

\n", "Our universal program is composed of a few sub-programs.\n", "We shall illustrate the ideas behind several sub-programs by making a\n", "large chart. This chart shows just one example\n", "of how a universal program could work, when we take\n", "p\n", "to be the program \n", "\n", "$$ \n", "\\begin{array}{lcl} p & = & \\mathtt{1\\#\\#} + \\mathtt{write}\\\\\n", "& = & \\mathtt{1\\#1\\#\\#\\#\\#\\#111111111\\#\\#\\#11111\\#\\#\\#11\\#11\\#\\#11\\#\\#111111\\#\\#\\#\\#11\\#11\\#\\#111111111\\#\\#\\#\\#11\\#\\#\\#\\#\\#111111\\#\\#\\#111\\#\\#\\#1\\#\\#1111\\#\\#\\#\\#1\\#111111\\#\\#\\#\\#} \n", "\\end{array}\n", "$$\n", "\n", " \n", "
\n", "

\n", "Let's parse this program and number the \n", "instructions:\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", "
1 2 3 4 5 6 7 8 9
1## 1##### 111111111### 11111### 11# 11## 11## 111111#### 11#
10 11 12 13 14 15 16 17 18
11##111111111####11#####111111###111###1##1111####1#111111####
\n", "
\n", "
\n", "

\n", "What we are going to show is tables of what the various\n", "registers show after different parts of a run of a universal program\n", "u on this program 1# + write.\n", "We hasten to add that the universal program exhibited above\n", "does not conform to the tables. (This is because\n", "registers work differently in it. Also, the program\n", "above is designed to work even without our simplifying\n", "assumption.)\n", "

\n", "Here are the tables; we'll have some words below about them.\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", "
R1: the input program p p p p p p p p p p p p p p
R2: an instruction number 1n\n", " 1 1 11 11 11111 11111 16 16 17 17 18 18
R3: the nth instruction of p \n", " 1## 1##### 11# 11## 11## 16 ####
R4: the contents of R1 # #
R5: the contents of R2 1 \t1 1# \t1# 1## 1##
R6: the contents of R3
\n", "\n", "\n", "
\n", "continuing\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", "
R1: the input program p p p p p p p p p p p p p
R2: an instr number 1n\n", " 11 11 111 111 112 112 114 114 117 117 118 118
R3: the nth instruction of p \n", " 1##### 19 ### 11##### 111### 1# 16 ####
R4: the contents of R1 1 1
R5: the contents of R2 1## 1## 1## 1## 1## 1## 1## \t1## ## \t## ## ##
R6: the contents of R3
\n", "\n", "
\n", "and going further in the move2,1 part\n", "at the end of write\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", "
R1: the input program p p p p p p p p p p p p p
R2: an instruction number 1n\n", " 112 112 115 115 116 116 112 112 115 115 116 116
R3: the nth instruction of p \n", " 11##### 1## 14#### 11##### 1## 14####
R4: the contents of R1 1 1 1 1 1# 1# 1# 1# 1# 1# 1## 1##
R5: the contents of R2 ## ## # # # # # \t# \t
R6: the contents of R3
\n", "\n", "
\n", "

\n", "and concluding\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", "
R1: the input program p p p p p p 1##
R2: an instruction number 1n\n", " 112 112 113 113 119
R3: the nth instruction of p \n", " 11##### 16 ###
R4: the contents of R1 1## 1## 1## 1## 1##
R5: the contents of R2
R6: the contents of R3
\n", "\n", "As promised, here are some words of explanation.\n", "

\n", "As you can see, there are four different colors of the columns.\n", "\n", "

\n", "\n", " \n", " \n", " \n", " \n", "
orange: starting out by pre-processing the input (if desired) and putting 1 in R2
beige: put into R3 the nth instruction of the program in R1, where 1n is in R2
green: execute the action in R3, but using R4 instead of R1, R5 instead of R2, and R6 instead of R3
yellow: finishing up by moving and clearing the relevant registers
\n", "
\n", "

\n", "The colors indicate the sub-programs of u.\n", "The columns themselves indicate the register contents when one\n", "of the sub-programs begins.\n", "

\n", "The first color shown is orange.\n", "This is the the easiest to explain. The orange sub-program could be 11#. \n", "This indicates that at the\n", "very beginning of the execution of\n", "the input program, the instruction to look at first is instruction 1. But if you decide to pre-process the input program (see below), then the orange sup-program would do this as well.\n", "

\n", "The beige columns alternate with the green columns.\n", "The purpose of the beige program is to take the input program\n", "(in R1) and the next instruction number (R2), and to\n", "look up the appropriate \n", "instruction and put it into R3. But we need to be sure that the contents\n", "of R1 and R2 are not destroyed at the end. The way to understand\n", "the beige columns is that they tell the contents of the various registers\n", "at the beginning of the operation of the \"beige\n", "sub-program\". You will need to write that sub-program.\n", "It is a fairly straightforward modification of a program which\n", "takes an input program q and a number n and gives the nth instruction of\n", "q. But you need to be\n", "sure that the output goes in R3, and that the input is preserved.\n", "

\n", "The main action of the steps is done in the green columns;\n", "more precisely, \n", "the columns shown are the beginnings of the\n", "\"green\" sub-program, and then the results of that sub-program\n", "are the beige columns which follow.\n", "The exact action depends on what kind of instruction is in R3 in \n", "the given green column. For example, if R3 has `≈, then\n", "in the next beige column we add a # to R5 (not R2: it is R5\n", "that models what is in R2 of the real machine when we run \n", "program). We also must add 1 to R2 in simulating the execution\n", "of 11#, since after 11#, we go to the very next instruction.\n", "This is how the green columns work when we execute an instruction\n", "11#. The other cases are left for you to think about.\n", "Note also that each time the green sub-program runs, R3 is emptied \n", "at the end.\n", "

\n", "The last column color is the yellow one at the very end.\n", "Before the yellow one starts up, the beige program\n", "has determined (in some sense) that \n", " our program $p$ has 18 instructions and we have \n", " come to a point where we ask for instruction 19. Thus, \n", " the input program has halted. We therefore want to\n", " take the contents of R1 as run by the input program\n", " (this is the word in R4), and move this to R1.\n", " Also, we would like to clear out the contents of\n", " whichever registers are not empty. We do this so that \n", " the program we are writing will itself come to a good halt\n", " on its input.\n", "
\n", "

\n", "It might seem silly to have R1 unchanged throughout.\n", "But this isn't really what is happening at all.\n", "In the course of the beige subprograms, parts of R1 are copied\n", "to other registers, and the copied back. So at the \n", "end of the beige sub-programs, we have the original\n", "program p back in R1. \n", "

\n", "Similarly, it might seem weird to have R6 completely unused\n", "in running a universal program on p. This is due\n", "to the fact that our program p only uses R1 and R2.\n", "If we worked with an example program that used R3, then R6\n", "would not have remained empty in the tables.\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "Vq9XIPJ-3JVP" }, "source": [ "## Coding unboundedly many registers into one\n", "\n", "The simplified form of the universal program that we just saw could be modified to work on programs with any fixed finite number of registers. But we want one universal programs that works on *all* programs, without a pre-established bound. For this, we need a new idea. \n", "\n", "We now call upon a technique introduced in a separate notebook in this course, the technique of [two-by-two encoding](two_by_two.ipynb). That notebook shows how we can add an *end of register marker* to R1, and the work with a simple encoding of symbols by pairs. We took the end of register marker to be ```##```, and we encoded ```1``` by ```11``` and ```#``` by ```1#```. \n", "\n", "All of that work was for R1 alone. But we could do the same work for all of the other registers. \n", "\n", "Following this, the idea is to simply run all of the encoded registers into one. \n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "frwGL8oj9fWQ" }, "source": [ "For an example of what we mean, suppose that we were dealing with the following snapshot:\n", "\n", "

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
R1: 11# R2: R3: ## R4: R5: R6: 1 R7: #R8: ##1
\n", "
\n", "\n", "(We understand also that all of the other registers are empty.)\n", "\n", "Encoding things as we have explained allows us to code the eight registers, as in the table below:\n", "\n", "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Contents R1: 11# R2:     R3: ## R4: R5: R6: 1 R7: #R8: ##1
Encoded as11111##### 1#1### ####11## 1# ##1#1#11##
\n", "
\n", "\n", "One important point is that the empty registers still get an end-of-register marker ```##```.\n", "\n", "Therefore we would encode the contents of these registers by the single word\n", "\n", "```11 11 1# ## ## 1# 1# ## ## ## 11 ## 1# ## 1# 1# 11 ##```\n", "\n", "Without spaces, this is\n", "\n", "```11111#####1#1#######11##1###1#1#11##```\n", "\n", "The point is that with some additional work, we can use this single word as an encoded form of *all* the registers in our program." ] }, { "cell_type": "markdown", "metadata": { "id": "Dr3J2J9kxcde" }, "source": [ "" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "hFWesdv5xu3j" }, "source": [ "# Group project\n", "\n", "```{dropdown} Click here for a suggestion on how groups could work together to write a universal program.\n", "\n", "\n", "Every instructor and every class will be different, here is one plan that has worked for me.\n", "\n", "Make groups of 4 or 5 people. If someone prefer to work alone,\n", "then it would be ok to do so, but I think it would be better to work with others.\n", "

\n", "
\n", "

\n", "Here is what each group needs to do:\n", "

    \n", "
  1. Make a plan on how to divide up the work of writing the\n", "different sub-programs. The parts are not all equally hard.\n", "The beige program could be the hardest, especially if you follow \n", "my comment below on it.\n", "\n", "
  2. You will need to meet, or at least to email each other, so that\n", "you can be sure that the different sub-programs do what they are supposed to.\n", "\n", "
  3. You also will need to have a plan on how to assemble everything together.\n", "The various sub-programs will need to \"talk to each other\"\n", "via goto statments. \n", "One good way is \n", "to use the \n", "Sanity parser. And one way that probably does not work well would be \n", "to simply\n", "put two flowcharts together. \n", "
  4. The group overall will need to turn in a program along with an explanation of\n", "the various parts. You should say clearly what the parts do, and also give some\n", "examples of how they run. If you have made flowcharts, it would be good\n", "to hand those in as well. \n", "
  5. You should test your overall program. It would be good to run\n", "your program on 1#, on self, and on 1#1## + u.\n", "
  6. At various points, you will be tempted to worry about what would happen\n", "if the input program isn't tidy. (For example, what should your\n", "program do if the input program is just 1111#### ?)\n", "Strictly speaking, the universal program should itself diverge on this input.\n", "But for our purposes, it's fine to ignore this point.\n", " You need not worry about this at all, only about the case\n", "when the input program is tidy. \n", "
  7. Above, we worked with the simplifying assumption that\n", "the input program only uses R1, R2, and R3. You should get a program\n", "u that woks on all input programs. \n", "
  8. \n", " It is important to write well. \n", " Your goal should be to write something that could be understood by\n", " someone else. \n", "
\n", " \n", " ``` \n", " " ] }, { "cell_type": "markdown", "metadata": { "id": "EPtY2M-hzToK" }, "source": [ "" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "E-EX6Y880HB1" }, "source": [ "# Universal programs of more than one argument\n", "\n", "Here is a more general result based on what we have seen up to now.\n", "\n", "```{prf:theorem}\n", "For every natural number $n$ there is a program $u_n$ such that for all words $p$, $x_1$, $\\ldots$, $x_n$,\n", "\n", "$$\n", "[\\![ u_n]\\!](p,x_1, \\ldots, x_n)\\simeq [\\![p]\\!](x_1, \\ldots, x_n)\n", "$$\n", "```\n", "\n", "What we have seen is an explicit program $u_0$.\n", "\n", "The proof of the general fact is an exercise using $u_0$ and the $s^m_n$ Theorem." ] }, { "cell_type": "markdown", "metadata": { "id": "qJo6UhZO1r14" }, "source": [ "```{exercise}\n", "What happens if we run the universal program $u$ on the self-writing program $\\self$?\n", "\n", "Incidentally, running $u$ on $\\self$ takes 22,376,608 steps, whereas running $\\self$ on empty registers takes 3,322.\n", "```\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{exercise}\n", "Show that the sets $K$ and $K_0$ are computably enumerable, where\n", "\n", "$$\n", "\\begin{array}{lcl}\n", "K & = & \\{ p : [\\![ p ]\\!](p)\\!\\downarrow\\}\\\\\n", "K_0 & = & \\{ p : [\\![ p ]\\!](\\ )\\!\\downarrow\\}\\\\\n", "\\end{array}\n", "$$\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "btoU-e9g1rti" }, "source": [ "```{exercise}\n", "Write a program ```trade``` which looks like it trades places with its input in R1. (Of course, a program cannot literally trade places with its input. But here is what we mean: 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.)\n", "\n", "[Hint: You will need a universal program, and also an application of the Recursion Theorem.]\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "aDG-w5LO1ri3" }, "source": [ "```{exercise}\n", "Write a program ```self1``` which writes itself to R1 but only uses R1 itself (no other registers). \n", "This exercise requires a trick, since there is no program like ```diag``` which only uses one register.\n", "\n", "[Hint: you will need the technique of coding several registers into R1.]\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# An extra property of the universal program\n", "\n", "For use in several places, we need a technical remark about the universal prorgram $u$ which we can arrange. That is, the remark below is not a consequence of the specification of $u$ that we started with. It is not even a consequence of the outline of $u$ which we provided.\n", "But if you write $u$ the way we suggest, then the property below is either true, or one can arrange for it to hold.\n", "\n", "```{attention}\n", "We may take $u$ to have the following property: when run on a word $x$ in R1, the word in R1 is not empty at any point other than at the very end.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Only one more register than the inputs\n", "\n", "The work in this section can be used to prove the following result. \n", "\n", "```{prf:proposition}\n", ":label: one-more-register-halting\n", "\n", "For every $n$ and every program $p$, there is a program $q$ such that \n", "\n", "1. For all words $x_1$, $\\ldots$, $x_n$,\n", "\n", "\n", "$$\n", "[\\![p]\\!] (x_1, \\ldots, x_n) \\simeq [\\![q]\\!] (x_1, \\ldots, x_n) \n", "$$\n", "\n", "2. $q$ uses R1, $\\ldots$, R$n$, R$(n+1)$, and no other registers\n", "\n", "3. $q$ may be obtained computably from $p$ and $n$.\n", "\n", "```\n", "\n", "Taking $n = 0$, it shows that when running a register machine program $p$ on no inputs, we may assume that the program uses only one register. In particular, we have an undecidability result:\n", "\n", "```{prf:proposition}\n", ":label: one-register-halting\n", "\n", "Let $A$ be the set of register machine programs which are tidy and which only use R1.\n", "\n", "Let $K^1$ be $\\{ p \\in A : [\\![p]\\!](\\ )\\!\\!\\downarrow\\}$\n", "\n", "Then $K_0 \\leq_m K^1$.\n", "\n", "\n", "```\n", "\n", "We are going to prove that $K_0$ is undecdiable in\n", "\n", "the section on the halting problem. It follows from the last result that the halting problem for register machine programs which are tidy and which only use R1 is undecidable.\n", "\n", "\n", "We are going to put the proposition just above to good use when we prove the undecidability of Post's correspondence problem and of tiling." ] } ], "metadata": { "colab": { "authorship_tag": "ABX9TyP/f3oLHI9gbYupphFqO3wd", "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 }