!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##
We have already seen computability on an intuitive or informal level. This intuitive level is both the right level for our work, and at the same time the wrong level. What we mean here is that for some things, working intuitively is exactly what we want to do. For other things, it is not nearly precise or specific enough. And for those, this book goes into a rather detailed set of definitions.
A word for us will be a sequence of strings using the characters 1
and #
. For example, 1##1
is a word, as is the empty word \(\varepsilon\). Words must be finite.
A register is a place that stores words. A register machine is a collection of registers.
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 1#
shortly. The idea is that the register machine starts with a few words in the registers, proceeds according to the program, and (if all goes well) eventually halts,.
The 1#
instruction set#
We list below the full set of instructions of 1#
. There are five instruction types.
Attention
When we use superscripts and write, for example, 1^m #^n
we mean \(m\) copies of the symbol 1
followed by \(n\) copies of the symbol #
. For example,
1^15 #^4
abbreviates 111111111111111####
There are only five kinds of 1#
instructions.
We begin with the first two kinds of instructions, those that end in #
and those that end in ##
.
Instruction |
Meaning |
---|---|
1# |
Add 1 to the right end of R1 |
11# |
Add 1 to the right end of R2 |
111# |
Add 1 to the right end of R3 |
Instruction |
Meaning |
---|---|
1## |
Add # to the right end of R1 |
11## |
Add # to the right end of R2 |
111## |
Add # to the right end of R3 |
We can summarize the two kinds of instructions which we have seen, and also extend them:
Instruction |
Meaning |
---|---|
1^n # |
Add 1 to Rn |
1^n ## |
Add # to Rn |
The programs of 1#
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:
Instruction |
Meaning |
---|---|
1^n ### |
Go forward n instructions in the program |
1^n #### |
Go backward n instructions in the program |
Here is the last kind of instruction:
Instruction |
Meaning |
---|---|
1^n ##### |
Cases on register n |
Here is what it does:
If Rn is empty, we go to the very next instruction.
If the first symbol of Rn is 1
, we delete that symbol and go to the second instruction after the case instruction.
If the first symbol of Rn is #
, we delete that symbol and go to the third instruction after the case instruction.

What are programs?#
Definition 4
A program is a finite sequence of instructions run together. Usually we insist that programs be nonempty.
We have already been using this terminology. For example, we saw
11#####111111###111###1##1111####1#111111####
near the top of this notebook. This is the concatenation of the following sequence of seven instructions:
(11#####
, 111111###
, 111###
, 1##
, 1111####
, 1#
, 111111####
)
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 1#
.
Incidentally, spaces are not significant in the interpreter above, or in the work we’ll turn to shortly. You may enter programs with spaces.
Important
Any sequence of 1#
instructions run together as a single word is a program.
Spaces inside do not matter.
Example
Here is a program:
\(\one\one\hash\one\one\hash\hash\hash\one\one\hash\hash\hash\hash\one\hash\hash\)
It is four instructions concatenated together.
The first instruction, \(\one\one\hash\), adds \(\one\) to R2. The second instruction says “go forward two instructions”, so we skip the next instruction (\(\one\one\hash\hash\hash\hash\)) and go to the last instruction \(\one\hash\hash\). This adds \(\hash\) to R1.
Exercise 22
Write a program which, when started with all registers empty, gives 1#
in R1 and R2, #1
in R3, and the other registers empty.
Important
Words have to be finite, and so programs also must be finite. Further, each program \(p\) of 1#
can only mention finitely many registers.
(That is, there is a finite set \(F\subseteq \N\) such that if
1^k #
is an instruction in \(p\), then \(k\in F\);
if 1^k ##
is an instruction in \(p\), then \(k\in F\);
and 1^k #####
is an instruction in \(p\), then \(k\in F\).)

Exercise 23
If you know about formal language theory, verify that the set of 1#
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 1^n #####
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.