It is not absolutely necessary to have the intepreter open as you work through this lesson. But it probably will help. If you do not have an interpreter, you should begin with the 1# instruction set. Those with an interpreter will enjoy the section on using the interpreter.

This lesson is written on a lower level than the lessons which come after it. The only abstract concept comes at the end, as does the only and mathematical notation. The rest of the lesson is a concrete introduction to 1#.

If you are familiar with any machine model in the theory of computations, such as Turing Machines, or classical register machines, you probably will want to skim through this lesson quickly.

But this introductory lesson is really intended for people with no background on these matters. If this is you, please work slowly, doing the exercises as you go.

Please copy the following program of 1# into the program window in the middle of the interpreter.

A note on copying from the web page (or from text files) to the interpreter: With most current browsers, you should be able to copy and paste as usual. For other browsers, things are harder. For example, using Safari, one would highlight the area to be copied, click on it, hold down the clicker and then drag the image to the 1# Interpreter. I would be interested to hear of others' experiences with copying to the interpreter.

Now enter some words in the input registers on the left. At first, it will be best to only enter words in the first two registers, R1 and R2. You must enter words composed of the symbols 1 and #, such as 11###11#1 and #1###1###111#11.

Next, run your program by clicking on one of the two buttons at the bottom. You can either run the interpreter in fast or slow mode. You should try out the two buttons to be able to tell which is which, and also you should try running the program very slowly by moving the indicator on the bottom right corner and by clicking the middle button of the three control buttons at the bottom.

You should then clear the input and output registers, and then enter some new words in R1 and R2. You might now enter some words in R3, R4, etc. to see what difference (if any) they make.

What you should find after doing this is that the output in R1 at the end is the input in R1 followed by the input in R2. And as a result of the same computation, R2 is emptied out. We usually will say concatenated instead of followed by.

The overall point is that the program 11#####111111###111###1##1111####1#111111#### may be run on words which are input in the registers. This program does not change when we run it, but the contents of the registers does change. Our first order of business is to understand programs like the one we've just seen. It turns out that this program is composed of seven instructions. We'll get to the instructions soon, but first we have an exercise for you to try.

Exercise 1 Here is another 1# program. It takes its input from the first two registers. Enter some words in R1 and R2 input boxes, and then run the program. Your job is to try to figure out what the program does. 1##### 11111111### 1111### 111## 1111## 11111#### 111# 1111# 11111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 1111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####

---

The 1# instruction set

So far, we have seen two programs of 1#. Programs are composed of instructions. In fact, programs are just sequences of instructions. The instructions could be written on separate lines, but they could also simply be run together to form a long word. At this point, we want to look at the five types of 1# instructions.

We begin our journey with the first two types of instructions of the language.

Instruction Meaning 1# Add 1 to R1 11# Add 1 to R2 111# Add 1 to R3 1111# Add 1 to R4

Instruction Meaning 1## Add # to R1 11## Add # to R2 111## Add # to R3 1111## Add # to R4

The group on the left are instructions that add a 1 to the end of the word in the specified register.

The ones on the right add a # to the end (the right side) of the word in the specified register.

The programs of 1# are just sequences of instructions run together.

There is no punctuation between the instructions. However, we do have an important comment.

Spaces and Comments

The interpreter ignores all spaces.

In addition, if you have a semicolon (;) in a line, the rest of that line is simply ignored. This way, you can add comments to programs.

For example, here is a program which we'll call p:

(We call this one p just to have a name for it; the letter stands for ``program.'') Programs of 1# are hard to read. But fortunately, there's an easy way to parse them into instructions. Everytime we see a # followed by a 1 we have the end of one instruction and the beginning of the next.

Going back to the program p above, we see that it parses into a sequence of four instructions:

Here is an explanation of what this program p does:

1. The first instruction, 1#, adds a 1 to R1.

2. Then 11## adds a # to R2

3. Then the third instruction again adds a # to R2.

4. Finally, 111## adds a # to R3.

Notice also that no other registers are affected.

For example, suppose we start with 1 in R1 and R2, 1# in R3, and the other registers empty. If we run our program p from above, we would end up with 11 in R1, ## R2, #1# in R3, and the other registers empty.

Exercise 2 Again, start with 1 in R1 and R2, 1# in R3, and the other registers empty. What happens in each register if we run 111##? You can try to figure this out for yourself, and then check your work by actually running the program.

Exercise 3 As before, start with 1 in R1 and R2, 1# in R3, and the other registers empty. What happens in each register if we run the same program p from above?

Exercise 4 Write a program which, when started with all registers empty, gives 1 in R1 and R2, 1# in R3, and the other registers empty.

The instructions in our two tables above were just samples. If you want to add a # to R15, you would use

(Incidentally, most of the instructions in this tutorial use only the first four registers. But you should know how to the meaning all of the instructions in the language.)

To state the instructions in a general way, we need a notational agreement.

"n in unary" and 1n both mean n 1s in a row.

So the succinct statement of the instructions to add symbols to the ends of registers is

Please remember: all adding is done on the right ends of the registers.

Transfer Instructions

Our next instructions move us around in a program.
Here is what they look like:

Instruction Meaning 1### Go forward 1 11### Go forward 2 111### Go forward 3 1111### Go forward 4

Instruction Meaning 1#### Go backward 1 11#### Go backward 2 111#### Go backward 3 1111#### Go backward 4

As before, you should understand the tables as providing examples:

in general we would write n in unary followed by ### to transfer forward n instructions,
and n in unary followed by #### to transfer backward n instructions.

Here is how this all works. Let's consider a sample program like

We'll call this program q.

Just as before, we start by parsing q as a list of instructions:

The first instruction of q adds a 1 to the end of whatever is in R2.
The second then transfers us to the sixth instruction, which transfers us back to the third.
Then we add 1 to R1. After this we add 1 to R2.
Then we arrive at the fifth instruction. This sends us forward 2, beyond the end of q.
As we'll soon see, this last point indicates that our program q halts.

Please remember: transfers in a program count either forward or backward from the current instruction. For forward transfers, start a count with 1 being the next instruction. For backward transfers, start with 1 being the previous instruction.

Infinite loops

Here's a simple 1# program: 1###1####.
It has two instructions.

The first instruction is to transfer ahead one instruction, and the second is to go back one instruction.

Executing this program puts the machine in an infinite loop.

You can try to run this program yourself on the simulator. Note that it catches this loop. But for bigger ones, the simulator will not detect the loop.

Can you think of other programs that would go into infinite loops?

Please remember: there is a stop button on the interpreter!

How programs halt

We have just seen programs with infinite loops. Such programs never finish. For all of our purposes in this tutorial, we are mainly interested in programs which do finish. Actually, we are interested in programs which finish in a special way.

We say that a program p halts if at some point during the execution of p, the control transfers to right below the last instruction of p. In more detail, suppose that p has n instructions. The formal definition is given below, after we discuss the remaining types of instructions.

In contrast, we say that p stops improperly if at some point during the execution of p, the control tranfers either to a point before the beginning of p or to points more than one instruction beyond the last instruction of p.

To see the difference, consider the following two programs:

11### Go forward 2 1# Add 1 to R1

111### Go forward 3 1# Add 1 to R1

The program on the left halts, while the one on the right stops improperly.

Exercise 5 Which of the following programs halt? Which stop improperly? 11###111###1#### 11###111###11#### 11###111###111#### 1111###1111###1####11###11#### [It would be better to try to solve this problem without running the programs.]

Please remember: the only way for a program p to halt is when control is transferred to just after the last instruction of p.

Case instructions

We now come to the last type of instructions in our little language 1#.

These are the most complicated instructions of all. But this means that after you learn about them, you've mastered the whole language.

Here are examples of what the case instructions look like:

The general idea behind them is that one whatever register is mentioned. Either it is empty, or the first symbol is 1, or the first symbol is #. We then continue the program according to which alternative holds. Here is how case instructions work:

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.

Halting: the formal definitions

There are five ways that p could halt.

1. Instruction n of p (the last instruction) is of the form 1^k# or 1^k##, and at some point in the run of p, we reach this last instruction.
2. Some instruction of p, say instruction number i, is of the form 1^k###; and also i + k = n + 1; and finally that at some point in the run of p, we reach instruction i.
3. Instruction n of p (the last instruction) is of the form form 1^k#####, and at some point in the run of p, we reach this last instruction with Rk empty.
4. Instruction n-1 of p (the next-to-last instruction) is of the form form 1^k#####, and at some point in the run of p, we reach this instruction with Rk containing a word beginning with 1.
5. Instruction n-2 of p (the second-to-last instruction) is of the form form 1^k#####, and at some point in the run of p, we reach this instruction with Rk containing a word beginning with #.

Programs to pop the first element off of registers

We now turn to some simple example programs. This topic is pursued more deeply in the lessons on arithmetic and programs which write programs.

One of the simplest programs is pop₁, a program to pop the first symbol from the word in R1. The remaining word will remain in R1. (If R1 is empty, the program will not do anything.)

The program above does what we want. There are other ways to do the same thing. For example, the last instruction 1### is not really needed. (Please think about this.) So we could also write pop₁ as

We can modify this to get a program pop₂ that pops the first symbol from R2: change the first instruction from 1##### to 11#####.

Programs to move register contents

Here is a program called move_2,1.
It writes the contents of R2 onto the end of R1, emptying R2 in the process.

Here it is again, parsed and annotated:

As you can see, we've color-coded this program differently than previous ones. The light-blue and tan regions are tiny sub-programs, and the colors help us to keep this straight.

The program move_2,1 is a big loop.

If R2 is empty, it halts.

If the first symbol of R2 is a 1, then the second instruction after the case instruction at the top transfers us down to the tan region. This part of the program would then add a 1 to R1 and return to the very beginning of the program.

If the first symbol of R2 is a #, then the case instruction at the top transfers us straight to the light-blue region. This part of the program would then add a # to R1 and return to the very beginning of the program.

The point is that by going around loop repeatedly, we transfer the contents of R2 symbol-by-symbol to R1.

Similarly, whenever m and n are different numbers, we can build a program move_m,n . This program would write the contents of Rm onto the end of Rn, emptying Rm in the process.

Exercise 6 Write move3,1 by modifying move2,1 above. Test your program to be sure it is correct. Then exhibit move1,2. This is an important exercise, since the programs movem,n (with various subscripts m and n) will be used throughout the rest of these lessons.

Exercise 7 Write a program that clears out R1, leaving it empty.

Exercise 8 Write a program that clears R3 and then swaps the contents of R1 and R2 (using the now-empty R3).

Exercise 9 Write a program p that adds a 1 at the beginning of R1, assuming that R2 is empty. Of course, you may use R2!

Programs to copy register contents

The difference between moving and copying for us is that when a register's contents are moved, the register is left empty; but if the contents are copied, then the register is left at the end with exactly what it had at the beginning.

Here is the idea behind copying Rm to Rn. We use an auxilliary register, say Rp. We move Rm into Rn and Rp at the same time, and then be move Rp back to Rm. Of course, when we do this, we should have Rp empty to start with.

Here is our program:

Here it is written out:

1m##### 11111111### 1111### 1n## 1p## 11111#### 1n# 1p# 11111111#### 1p ##### 111111### 111### 1m## 1111#### 1m# 111111####

To use this, you only need to fill in actual numbers in unary for m, n, and p.

We call this program copy_m,n,p. And we say that it copies Rm to Rn using Rp as a temporary storage register.

Programs and the functions they compute

Now we have our 1# instruction set. And know what programs of 1# are and how they work. These programs are the the central objects of study. Actually, we are interested not just in the programs themselves but in what they compute. (Interestingly enough, the classical theory of computation has little to say about how programs work. This is because the theory is not primarily about this topic in the first place.)

We call the set {1,#} our alphabet, and we use the letter A for it. We know that it is odd to call such a small set an "alphabet", even more so when that set doesn't have any letters in it!
But this usage is standard, and so we'll stick to it. When used in situations like ours, the word "alphabet" just means a set that you use to build words from. But if {1,#} is our alphabet, what in the world are our words?!

A word is just a sequence of symbols from our alphabet.
(In contrast to most uses in mathematics and computer science, our words will all be non-empty.) So examples of words include 11#, and also ###.

At this point, we have seen all of the different instructions of 1#. We have also seen programs.

It is worthwhile to be clear about the difference between instructions and programs:

• Instructions are single steps in programs.

• A program is just a long list of instructions, run together to make a big word.

A program can contain a small number of instructions, or a large number of them. So far, we have only seen programs with six instructions or fewer. But we can also have programs with a zillion instructions. You might wind up writing such programs as you work through this tutorial. Every program can be parsed, or decomposed, into its instructions.

Every program p gives us a function called φ_p on words.

Suppose that when we run the program p with the word x in R1 and all other registers empty, then the register machine eventually halts with y in R1 and all other registers empty. If this happens, then we say that φp(x) = y. In all other cases (if p does not halt with x in R1, or if it halts but not all of the registers besides R1 are empty), then we say that φp(x) is undefined.

This definition calls for a set of examples.

1. φ_1#(11#) = 11#1, because running the program 1# on 11# adds a 1 at the end.

2. φ_1#(##1#1) = ##1#11. The reasoning is similar.

3. φ_1###1####(1) is undefined. The reason is that 1###1#### goes into an infinite loop.

4. Indeed φ_1###1####(x) is undefined for all x.

5. You might like to think about why each of the following is true:

   1. φ_1###(x) = x for all x.

   2. φ_11###(x) is undefined for all x.

Programs as functions of more than one argument

In our work just above, we started with a program, say p, and then showed how our machine leads to a function from words to words φ_p. Each function φ_p was regarded as a function of one argument. But in mathematics and computer science we see functions of more than one argument all the time: addition and multiplication of numbers, for example.

What we want to do is to show how each program p of 1# also gives a function of two word arguments, and also a function of three, etc.

Given a word x, suppose that if we the program p with x1 in R1, x2 in R2, . . ., xn in Rn, then the program eventually halts with y in R1 and all other registers empty, then we say that φpn(x1,...,xn) = y. In all other cases (if p does not halt with x in R1, or if it halts but not all of the registers besides R1 are empty), then we say that φpn(x1,...,xn) = y. is undefined.

The full instruction set of 1#

For your reference, here is a table that lists the full set of instructions of 1#.

Anytime you want it, you can get a separate window with a 1# language summary. Use the menu in the left sidebar at the top of the page.

Exercise 10 (Just for your amusement) At first glance, it might seem that every string of 1s and #s is a valid program of 1#. But this is not quite right: 1###### is not a valid program, for example. Find a simple way to extend the language so that this string, and all strings of 1s and #s are valid programs. (This is not an important exercise, and nothing we do depends on it.)