Programs for Programs
IU Relief
Skip Navigation
1#: A Text Register Introduction to Computability Theory

red horizontal line
red horizontal line
red horizontal line
Programs for Programs

LESSON Three


write


smn


Other useful programs

Welcome

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.




write

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.
In symbols, φ φwrite(x)( ) = x. [Yes, that really is φ with a big subscript φwrite(x), applied to nothing.]

The official program is

1#####111111111###11111###11#11##11##111111####11#11##
111111111####11### ##111111###111###1##1111####1#111111####

and the explicated parse is

1##### Cases on R1
111111111### Go forward 9: to move2,1 part
11111###Go forward 5: to the brown part
11# Add 1 to R2: 1## adds # to R1
11## Add # to R2
11## Add # to R2
111111#### Go backward 6 (to the top)
11# Add 1 to R2: 1# adds 1 to R1
11## Add # to R2
111111111#### Go backward 9 (to the top)
move2,1 from Lesson 1

Note that the last "instruction" of this program is really a program of its own. That is, by move2,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.




smn

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

move1,2 + φwrite(111111) + div

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,

11#111## + 1#####111# = 11#111## 1#####111#

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

move1,2 + 1#1#1#1#1#1# + div

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

move1,2 + φwrite(1111111111111) + div

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 1m 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 move1,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

write + move1,2 + φwrite(move1,2) + move2,1 + φwrite(div)

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:

R1 R2
at the start 111
after write 1#1#1#
after move1,2 1#1#1#
after φwrite(move1,2) move1,2 1#1#1#
after move2,1 move1,2 + 1#1#1#
after φwrite(div) move1,2 + 1#1#1# + div

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 s11 with the following properties:

  1. When s11 is started with p in R1 and q in R2, and R3 and R4 empty, the machine eventually halts. Let x = φs11(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 s11 to be

move1,3 + move2,1 + write + move1,2 + φwrite(move1,2) + move2,1 + move3,1

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

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

R1 R2 R3
at the start p q
after move1,3 q p
after move2,1 q p
after write φwrite(q) p
after move1,2 φwrite(q) p
after φwrite(move1,2) move1,2 φwrite(q) p
after move2,1 move1,2 + φwrite(q) p
after move3,1 move1,2 + φwrite(q) + p

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 move1,3 and not move1,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 s11 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:

R1 R2
at the start r
after move1,2 r
after φwrite(q) q r
after p φp(q,r)

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 s11, but with the difference that it takes three arguments instead of two. The new program is called s12. We want it to have the following properties:

  1. When s12 is started with p in R1, q1 in R2, q2 in R3, and all the rest empty, the machine eventually halts. Let x = φs12(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.





Other useful programs

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:

1##### 1111111### 11#### 11# 1##### 111### 111111#### 111####

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.

1##### Cases on R1
forward to R1 is empty
forward to R1 starts with a 1
forward to R1 starts with a #
1##### R1 is empty and Cases on R2
forward to R2 is empty
forward to R2 starts with a 1
forward to R2 starts with a #
1##### R1 starts with a 1 and Cases on R2
forward to R2 is empty
forward to R2 starts with a 1
forward to R2 starts with a #
1##### R1 starts with a 1 and Cases on R2
forward to R2 is empty
forward to R2 starts with a 1
forward to R2 starts with a #



Next, we have a program called bump. This program takes a program p in R1 and a unary number 1n 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.

1# 1## 1## 1## 1## 1## 1## 1##### 1### 1### 1### 1##### 1# 11### 111### 1# 11111#### 1##### 1# 11### 1111111111 11### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1111111111 1111111111#### 1##### 1# 11### 1111111111 111### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1## 1111111111 11111111111 11111111111 1111#### 1##### 1# 11### 111111### 1# 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11#### 1##### 1# 11### 1111111### 1# 1## 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11111111111 1#### 1##### 1# 11### 1111111111 111111### 1# 11## 11##### 1# 11### 1111### 1# 11# 111111#### 1## 1## 1## 1## 1## 1111111111 11111111111 11111111111 11111111111 11111111111 11111111111 111111111####

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.

1# 11## 111### 1111#### 11111#####
111# 1111 ## 111### 1111#### 1111111#####

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 φbumpbump(p,n),m) ?



Last updated: 25 September 2007
Comments: lsm at cs dot indiana.edu
Copyright 2014, The Trustees of Indiana University
Copyright Complaints