Tidy programs
Contents
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 1
Every program is strongly equivalent to a tidy program.
Exercise 24
Prove this proposition. (Alternatively, write a program in either Python or 1# which found a tidy version of an input program.)
Exercise 25
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 26
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 27
Show that the union of two computably enumerable sets is computably enumerable.
[Hint: use Exercise 26.]