Tidy programs#
We next come to an important definition concerning programs.
When a program is executed, each line either transers control to another line, or to some “line” outside the program. If line k is an instruction of the form 1^k# or 1^k##, then after line k is executed we go to line k + 1. Of course, both of these statements assume that there is a line k + 1. If line k is the last line of the program, then “line k+1” does not exist. But in this case, we say that the program has halted.
A similar statement holds for the transfer instructions.
If line k is 1^m ###, then after line k is executed we go to line k + m, provided there is such a line in the program. If the program has N lines and k + m = N+1, then after line k is executed, the program has halted. If k + m > N+1, then the program has not halted; it is stuck.
!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *
Here are some examples of what we are after. if the last line of a program \(p\) is 1#, then that line transfers control outside of \(p\), but only one line below the end. On the other hand, if a program \(q\) has exactly \(10\) lines, then we do not want line \(8\) to be 1111###, since executing this line would take us to “line 12”. So a run of \(q\) which reached line \(8\) would not halt.
We would prefer to rewrite \(q\) to point to an infinite loop inside of the program.
(There are reasons that we prefer programs to have explicit infinite loops instead of pointing to unwanted places. One such reason appears in on-tidiness below. Other reasons for this preference will be revealed in due course.)
Informally, we say that a program \(p\) is tidy if no instruction can possibly take us outside the program, except for going “one instruction below the end” of \(p\).
What we are after here is a formal definition of tidiness.
Definition
Suppose that \(p\) is a program with \(N\) lines. Here are the requirements for \(p\) to be tidy:
(a) If line \(i\) is a forward transfer instruction
1\(k\)###, then \(i +k \leq N+1\).
(b) If line \(i\) is a backward transfer instruction 1\(k\)####, then \(i-k \geq 1\).
(c) If line \(i\) is a case instruction 1\(k\)#####, then \(k+2 \leq N\).
Here is a comment on condition (c).
Suppose that \(p\) had \(N\) lines, and line \(N\) were a case instruction
1\(k\)#####. If Rk stared with a #, then executing 1\(k\)##### would take us to line \(N+3\), and there is no such line.
For the same reason, lines \(N-1\) and \(N-2\) cannot be case instructions.
Strong equivalence to tidy programs#
Proposition 3
Every program is strongly equivalent to a tidy program.
Exercise 39
Prove this proposition. (Alternatively, write a program in either Python or 1# which found a tidy version of an input program.)
Exercise 40
Prove that every program is strongly equivalent to a program in which the none of the last three instructions are case instructions 1^n #^5.
(I need to write out the solution in full here.)
Exercise 41
If \(p\) is tidy, show that \(p\) is strongly equivalent to any program of the form
1### 1### \(\cdots\) 1### p 1### 1### \(\cdots\) 1###
Show that all three parts of the definition of tidiness are needed in order to show this fact.
Exercise 42
Let \(q\) be tidy, and assume that \([\![ p ]\!](x) \simeq y\). Show that the following are equivalent:
\([\![ p+q ]\!](x)\downarrow\).
\([\![ q ]\!](y)\downarrow\).
\(([\![ q ]\!]\circ [\![ p ]\!])(x)\downarrow\).
(Joshua Burns) Show that in general we need \(q\) to be tidy to have (1)\(\Rightarrow\)(2).
Exercise 43
Let \(p\) be a tidy program. Show that there is a program \(q\) with the following properties:
(a) \(q\) is strongly equivalent to \(p\).
(b) In \(q\), every backward-transfer instruction points to the top of the program. That is, if line \(i\) of \(q\) is \(\one^k \hash^4\), then \(k = i-1\).
Exercise 44
Show that the union of two computably enumerable sets is computably enumerable.
[Hint: use Exercise 43.]