At this point, we have seen the basics of our language 1#, both the syntax (the form of the instructions) and the semantics (the meanings of programs).

Our last lesson was on programs that compute familiar functions from arithmetic. Much of that discussion was a detour from our main material, and at this point we resume the main track.

The central feature of 1# is that the instructions are the same kinds of things as the contents of the registers. Here is what we mean on this: recall that we have a set {1, #} called our alphabet.

All of the instructions are words over 1,#, and all of the programs of 1# are also words over this alphabet 1,#. (This just means that they are non-empty sequences of symbols from the alphabet.) The contents of the registers are also words over the same alphabet 1,#. (To appreciate this point, think about a language whose commands were written with the usual alphabet symbols a, b, c, . . and yet whose programs output numbers.)

1# was designed to be as simple as possible and yet have the feature we just mentioned, that the words written to registers are essentially the same as the instructions and programs.
This suggests that one can write programs that write or modify programs. This is the main topic of this part of our tutorial.

We start with a program write with the following properties:

1. When write is started with x in R1 and R2 empty, we eventually halt with a word y = φ_write(x) in R1 and all other registers empty.
2. Running y with R1 empty results in x back in R1 and all other registers empty.

The official program is

Note that the last "instruction" of this program is really a program of its own. That is, by move_2,1 we mean the program with that name from Lesson 1.

It should be noted that write reads from R1 and writes to R2; it makes no use of any other register.

Once again, the key property of write is that

φφwrite(x)( ) = x.

Exercise 1 Building on your solution to Exercise 5 of Lesson 1, what is &phiwrite(move3,1) ?

Exercise 2 Is &phiwrite(x) always a program, even if x is a word which is not a program?

Exercise 3 Modify write to get a program write-to-2 with the following feature: If write-to-2 is started with x in R1 and R2 empty, we eventually halt with a word y = &phi write-to-2(x) in R2 and all other registers empty; moreover, running y with R2 empty results in x back in R2 (not R1) and all other registers empty.

You wrote a program div that did division. For example,

φ_div(111,11) = 1#1.

φ_div(111111,111) = 11#.

Suppose we now want to write a program called div-6-by. It should take an input in R1 and divide 6 by that input. So we should have

φ_div-6-by(11) = 111#

φ_div-6-by(1111) = 1#11

How can we get this program div-6-by? You are encouraged to think of this yourself, and especially to do so as we continue this discussion. And for now, one way to get div-6-by would be as

Here is an explanation of the notation above. We use + as a symbol for concatenation of words. This just means that x + y is the word x followed by the word y. For another example,

Recall as well that φ_write(111111) = 1#1#1#1#1#1. So we could also say that we take div-6-by to be

At this point, we have seen div-6-by. And now, let us ask about a similar program, div-5-by. This program would take an input and divide 5 by it. Once we understand what this means, we can see that it should be

Similarly, div-13-by can be taken to be

And so on. What we really want at this point, is a program that takes a number m as input and outputs the program div-m-by. In other words, we want a program that we'll call div-me-by. It should behave as in the following examples:

φ_div-me-by(11111) = div-5-by.

φ_div-me-by(111111) = div-6-by.

In more detail, if we run div-me-by with 1^m in R1 and all other registers empty, then we eventually halt with the program div-m-by in R1, and all other registers are empty.

The idea is that div-me-by will take whatever is in R1,

run write on it (using R2 in the process),

then hide the result in R2,

then spit out move_1,2 into R1,

then copy R2 back on to the end of R1,

and finally spit out the program div onto the end of R1.

Following this idea, we may take div-me-by to be

Here is a chart that might help in understanding the parts of this program div-me-by. We show what happens when we run the program on 111:

The rows of the chart indicate the register contents after various parts ofthe program have been executed. As you can see, we end up with div-3-by in R1. Moreover, there is nothing special about the number 3 here.

We construct a program s₁¹ with the following properties:

1. When s₁¹ is started with p in R1 and q in R2, and R3 and R4 empty, the machine eventually halts. Let x = φ_s1¹(p,q) be the result.
2. If we then run x with r in R1, then the result is the same as when p is started with q in R1 and r in R2.

To state it again, this time in symbols rather than English,

When φs11(p,q) is started with r in R1, then the result is the same as when p is started with q in R1 and r in R2. Therefore φφs11(p,q) (r) = φp(q,r)

We take s₁¹ to be

Once again, we have used + above for the concatenation of several programs into one.

Note also that the third of the seven segments in s₁¹ is write, the program that we saw in Lesson 1; the fifth is the result of applying that program to move_1,2. Here is a chart which shows what is going on when we run s₁¹ with p in R1 and q in R2.

It might be worthwhile to note that write requires R2 to be empty when it starts, since it uses that register. This is one reason why the second segment in the overall program is move_1,3 and not move_1,2. The other reason is that at that point in the program, q is already in R2, and so it would be a big problem to forget this.

Finally, we'll check that that s₁¹ does the right thing. That is, if we take p and q as above to get φ_write(q) + p, and then if we run that program with r in R1, we should get the same thing as φ_p(q,r). Here is the verification of this:

We might mention that this chart doesn't show any of the steps of p in any way. In particular, running p on q and r might involve many registers besides R1 and R2.

At this point, we want to consider a program a bit like s₁¹, but with the difference that it takes three arguments instead of two. The new program is called s₁². We want it to have the following properties:

1. When s₁² is started with p in R1, q1 in R2, q2 in R3, and all the rest empty, the machine eventually halts. Let x = φ_s1²(p,q1, q2) be the result.
2. If we then run x with r in R1, then the result is the same as when p is started with q1 in R1 and q2 in R2, and r in R3.

Exercise 4 Modify the work we did on s11 to write s12. That is, make the same kinds of charts and carry out the same kind of checks. Please also be sure that whenever a program calls write that R2 is empty.

This lesson is about programs which are designed to run on programs. One of the lessons that working with a language like 1# is intended to teach is that there is no sharp separation between programs and data. Nevertheless, we can attempt an intuitive definition of a program working on programs. It is a program p which treats one or more of its arguments as programs. So such a program p would probably be built on some sort of parser for 1#. The fact that 1# is a very simple language (a regular language, in case you know this terminology) makes such programs relatively easy to write.

Please note again that what we are calling "programs for programs" have to run on all words, not just valid programs. But typically we don't care about what the programs in this section do to inputs which are not themselves programs.

In this section, we exhibit a few more programs on the topic of this lesson.

Here is a program length that takes a program in R1 and tells how many instructions it has, written out as a unary number:

The answer gets written to R2, and the original program is lost. If R1 does not contain a program, then we do not care what this program does.

It is worthwhile understanding this kind of program, since the ideas in it come up quite often. Instead of parsing and presenting that program, we'll look at a flowchart and then see how to fill it in to do what we want:

You may get the flowchart in pdf format by clicking here.

As you can see, it is often easier to think about programs by making a flowchart. Once you do that, there is a fairly straightforward way to convert the flowchart to a program:

First, add names to the nodes of your program. Every node should get a name of its own, with no sharing of names. In the example file, we used letters as the names of the nodes.

Next, make a list of the names. Be sure to put the name of the start node at the top, and the name of the end node at the bottom. Other than this, it is pretty much up to you how you want to list the nodes.

For each name corresponding to a case statement, you will need to put in the next three lines of the program. As you know, these correspond to whether the chosen register is empty, began with a 1, or began with a #. In some cases, you will be able to fill in those lines with the names of other nodes. But in most cases, these lines will be transfer statements. But at this point, you will be able to figure out the appropriate values of all of the transfer statements. Some will be forward transfers, and some will be backward transfers.

We also put down a table which is useful to have, for programs which proceed by taking elements from R1 and R2, and then deciding what to do based on both values.

Next, we have a program called bump. This program takes a program p in R1 and a unary number 1ⁿ in R2, and it returns a program which is just like p except that all of the register numbers have been "bumped up" by n.

As an example of how this is used, suppose we appy bump with R1 containing 1#11##111###1111####11111#####. This is the top line below.

Suppose we apply bump with R2 containing 11. We would get the second line above.
The added 1s are in red.

Note that we do not add 1s to the instructions for transferring forward or backward.

This program bump was used in Lesson 2 when we discussed primitive recursion. It would be a good exercise to write this program yourself. But the program itself is not going to reappear so often in later lessons. The program length will turn out to be more useful.

Exercise 5 Write a program p that tells whether a word x in R1 is a program of 1# or not. In more detail, you want p to behave as follows: for all words x, φp(x) = 1 if x is a valid program of 1#, and φp(x) = # if x is a not a valid program of 1#.

Exercise 6 Write a program p which writes move programs. In more detail, if m and n are different numbers in unary, we want φp(m,n) to be a program movem,n as we described it in Lesson 1. (If either m or n is not a unary numeral, then we don't care what φp(m,n) is.

Exercise 7 (A challenge problem) Write a program that takes a word in R1 and reverses it.

Exercise 8 What is φbump(φbump(p,n),m) ?