!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *
Instructions of 1##
Attention
Note for instructors
The book could begin here instead of with the previous chapter. In that case, one would return to one or more sections from the previous chapter on an as-needed basis. On the other hand, most of this chapter is crucial for what follows.
Computability can be studied on an intuitive or informal level before one sees definitions. This intuitive level is both the right level for our work, and at the same time the wrong level. That is, for some things, working intuitively is exactly what we want to do. For example, this was appropriate in the last chapter. For other things, it is not nearly precise or specific enough. And for those, this book goes into a rather detailed set of definitions, starting now.
A word for us will be a sequence of strings using the characters \(\onett\) and \(\hash\). For example, \(\onett\hash\hash\onett\) is a word, as is the empty word \(\varepsilon\). Words must be finite. We use \(\Words\) to denote the set of all words. We use letters like \(x\), \(y\), \(z\), \(u\), \(v\), \(p\), \(q\), etc. for words.
We deal a lot with (finite) sequences of words. A sequence of words \(x_1\), \(\ldots\), \(x_n\) is often denoted \(\overline{x}\) for short.
A register is a place that stores words. A register machine is a collection of registers indexed by nonzero natural numbers. These registers are called R1, R2, etc. The machine runs according to a program. Programs are comprised of instructions. We are going to describe instructions and programs in \(\onesharp\) shortly. The idea is that the register machine starts with input words in its registers – all but finitely many are \(\eps\) – proceeds according to the program, and (if all goes well) eventually halts with an output in R1.
The \(\onesharp\) instruction set#
The chart below contains the full set of instructions of \(\onesharp\). There are five instruction types.
Instruction |
Meaning |
|---|---|
1^n # |
Add 1 to Rn |
1^n ## |
Add # to Rn |
1^n ### |
Go forward n instructions |
1^n #### |
Go backward n instructions |
1^n ##### |
Cases on Rn |
We now discuss them.
Remark 1
When we use superscripts and write, for example, \(\onett^m \hash^n\) we mean \(m\) copies of the symbol \(\onett\) followed by \(n\) copies of the symbol \(\hash\). For example, \(\onett^{15} \hash^4\) abbreviates
There are only five kinds of \(\onesharp\) instructions. We begin with the first two kinds, those that end in \(\hash\) and those that end in \(\hash\hash\). For example, \(\onett\hash\) takes whatever word happens to be in R1 and adds a \(\onett\) to its right end. Similarly, \(\onett\onett\hash\) takes whatever word happens to be in R2 and adds a \(\onett\) to its right end. As for the instructions which end in \(\hash\hash\), such as \(\onett^5\hash\hash\), it would add \(\hash\) to the right end of R5.
The programs of \(\onesharp\) are just sequences of instructions run together. There is no punctuation between the instructions. To move around in a program, we have two other kinds of instructions: The instructions \(\onett^m \hash^3\) move forward. So if instruction \(15\) in a program happens to be \(\onett^8 \hash^3\), then when we execute it we next go to instruction \(15 + 8 = 23\). Similarly, The instructions \(\onett^m \hash^4\) move backward. If instruction \(31\) in a program happens to be \(\onett^2 \hash^4\), then when we execute it we next go to instruction \(31- 2 = 29\).
The last kind of instruction, \(\onett^n \hash^5\) is the most complicated. Here is what it does: If Rn is empty, we go to the very next instruction. If the first symbol of Rn is \(\onett\), we delete that symbol and go to the second instruction after the case instruction. If the first symbol of Rn is \(\hash\), we delete that symbol and go to the third instruction after the case instruction. The workings of these case instructions will be clarified through examples, and we will see several in the section on basic programs
What are programs?#
Definition
As mentioned, a program is a finite sequence of instructions run together to make a word.
Example
Here is a program:
It is four instructions concatenated together. The first instruction, \(\onett\onett\hash\), adds \(\onett\) to R2. The second instruction says “go forward two instructions,” so we skip the third instruction, \(\onett\onett\hash\hash\hash\hash\), and go to the fourth instruction, \(\onett\hash\hash\). This adds \(\hash\) to R1.
Examples
Here is another program:
This is the concatenation of the following sequence of seven instructions:
Dividing a program into instructions is a very easy form of parsing. In a real computer language, parsing is more difficult than it is for \(\onesharp\).
Exercise 24
Write a program which, when started with all registers empty, gives \(\onesharp\) in R1 and R2, \(\hash\onett\) in R3, and keeps the other registers empty.
Exercise 25
This problem is about the program \(p = \onett\onett\onett\hash\hash\).
Start with \(\onett\) in R1 and R2, \(\onett\hash\) in R3, and the other registers empty. What happens in each register if we run \(p\)?
Start with \(\onesharp\) in R1 and R3, \(\onett\) in R2 and R4, and the other registers empty. What happens in each register if we run \(p\)?
Here is an important point: Words have to be finite, and so programs also must be finite. Further, each program \(p\) of \(\onesharp\) can only mention finitely many registers. (That is, there is a finite set \(F\subseteq N\) such that if \(\onett^k \hash\) is an instruction in \(p\), then \(k\in F\); if \(\onett^k \hash\hash\) is an instruction in \(p\), then \(k\in F\); and \(\onett^k \hash^5\) is an instruction in \(p\), then \(k\in F\).)
Exercise 26
If you know about formal language theory, verify that the set of \(\onesharp\) programs is a regular language.
Reference#
The full set of instructions of 1##
Instruction |
Meaning |
|---|---|
1^n # |
Add 1 to Rn |
1^n ## |
Add # to Rn |
1^n ### |
Go forward n instructions |
1^n #### |
Go backward n instructions |
1^n ##### |
Cases on Rn |
All numbers in this chart are written in unary, and \(n\geq 1\).
Registers are processed as queues: symbols enter on the right and exit on the left.
The first two types of instructions add symbols to the right ends of the registers.
Here is a review of how the case instruction \(\onett^n \hash^5\) works.
If Rn is empty, we go to the very next instruction.
If the first symbol of Rn is \(\mathtt{1}\), we delete that symbol and go to the second instruction after the case instruction.
If the first symbol of Rn is \(\mathtt{\#}\), we delete that symbol and go to the third instruction after the case instruction.