!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.

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.