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

red horizontal line
red horizontal line
red horizontal line
Universal Programs

LESSON Six


Universal programs


A simplification and a plan


Class project


Coding all the registers in one


Universal programs of more than one argument


Exercises


Welcome

This lesson will teach you about universal programs: these are programs that take 1# programs as inputs and run them. More precisely, consider the following program u:

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

This program u has the following feature. Let p be any program of 1#, or indeed any word on {1,#}. Let x be any word on {1,#}, including possibly the empty word. Then the following are equivalent:

  1. If p is started with all empty registers, then eventually we halt with x in R1.
  2. If u is started with p in R1 and all other registers are empty, then eventually we halt with x in R1.

This means that if running p on all empty registers eventually gives some output in R1 (and all other registers empty), then that same output would be the result of running u with p in R1 and all other registers empty. And in the other direction, if running p with all empty registers gives some output, say x, in R1 (and all registers empty at the end), then we would get the same output x in R1 when we run u with p in R1 and all other registers empty.

Here is a specific example of this. Try running u with 1# 1## in R1. The result is 1#, and this is what happens when we run 1# 1## on all empty registers. So the universal program u takes 1# 1## and simulates a run of that program.

For another example, suppose we start u with self in R1 (and all other registers empty). You can check for yourself that we eventually get self in R1. (Note: the computation might take several minutes.) This confirms the basic property because running self with all registers empty gives self.

We can even run u on programs that contain u itself. For this, we return to our first example, concerning the word 1# 1##. As we know,

φu(1# 1##) = 1#.

Recall also that

φwrite(1# 1##) = 1# 1## 1# 1## 1##

It follows that

φ1# 1## 1# 1## 1## + u( ) = 1#.

And from this we conclude that

φu(1# 1## 1# 1## 1## + u) = 1#

This is something you can try for yourself.


The plan for this lesson

The goal of this lesson is for you to write a universal program yourself. The next sections guide you, using a series of exercises.

We hasten to make two remarks: first of all, it would be more instructive for you to forget about the rest of this lesson entirely and to just write your own universal program. But this most readers would probably appreciate the hints and will find enough of a challenge in the construction of a long working program. Second, the sections to come do not guide you to write a program that is exactly like u above. The u above was designed to be as short as possible. In fact, we leave you with a challenge: write a universal program with the smallest number of instructions. The one above has 300.




A simplification and a plan

We are going to simplify the requirements in order to make it easier to write a universal program. So we'll outline how to write a program that is close to a universal program, but not quite a universal program.

We'll write a program u that acts like a universal program, but only for programs which use only R1, R2, and R3. In more detail:

Let p be any program of 1# which only uses R1, R2, and R3. Let x be any word on {1,#}, including possibly the empty word. Then the following are equivalent:

  1. If p is started with all empty registers, then eventually we halt with x in R1.
  2. If u is started with p in R1 and all other registers are empty, then eventually we halt with x in R1.

Once again, the work of this section sketches a construction of such a program u. You will need to do much of the work yourself in actually getting the program from the sketch. And even when we have u, it will not be quite what we want for this lesson overall, because u will only behave right on programs which use the first three registers. Later on, we'll come back and drop this simplification to get a program which is truly universal.

At this point, we are ready to sketch a method for you to write a universal program subject to this simplification.

We are going to use registers as follows:

R1: the input program p
R2: an instruction number 1n
R3: the nth instruction of p
R4: the contents of R1
R5: the contents of R2
R6: the contents of R3

That is, we are going to simulate the computation of a register machine on a program p by using six registers. Our universal program u is what does the simulation, and it works step-by-step. That is, u mimics what a register machine would really do. The only difference is that one step of a real register machine would be done by many steps of our universal program.

The registers above hold what is sometimes called a snapshot of a register machine run. This means that they hold all of the relevant information about a register machine computation at one particular point in time: they tell what program is running, which instruction would be run next and what number instruction it is, and also the contents of all of the registers that the program is using. Now a real register machine goes from snapshot to snapshot in one step, but the universal machine that we are building will take many steps to go from one snapshot to the next.

Our universal program is composed of a few sub-programs. We shall illustrate the ideas behind several sub-programs by making a large chart. This chart shows just one example of how a universal program could work, when we take p to be the prorgram

1## + write

Now to make life easier, we'll write out this program and indicate the instruction numbers above them:

1 2 3 4 5 6 7 8 9
1## 1##### 111111111### 11111### 11# 11## 11## 111111#### 11#
10 11 12 13 14 15 16 17 18
11## 111111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####

What we are going to show is tables of what the various registers show after different parts of a run of a universal program u on this program 1## + write. We hasten to add that the universal program exhibited above does not conform to the tables. (This is because registers work differently in it. Also, the program above is designed to work even without our simplifying assumption.)

Here are the tables; we'll have some words below about them.
R1: the input program p p p p p p p p p p p p p p
R2: an instruction number 1n 1 1 11 11 11111 11111 16 16 17 17 18 18
R3: the nth instruction of p 1## 1##### 11# 11## 11## 16 ####
R4: the contents of R1 # #
R5: the contents of R2 1 1 1# 1# 1## 1##
R6: the contents of R3

continuing
R1: the input program p p p p p p p p p p p p p
R2: an instr number 1n 11 11 111 111 112 112 114 114 117 117 118 118
R3: the nth instruction of p 1##### 19 ### 11##### 111### 1# 16 ####
R4: the contents of R1 1 1
R5: the contents of R2 1## 1## 1## 1## 1## 1## 1## 1## ## ## ## ##
R6: the contents of R3

and going further in the move2,1 part at the end of write
R1: the input program p p p p p p p p p p p p p
R2: an instruction number 1n 112 112 115 115 116 116 112 112 115 115 116 116
R3: the nth instruction of p 11##### 1## 14#### 11##### 1## 14####
R4: the contents of R1 1 1 1 1 1# 1# 1# 1# 1# 1# 1## 1##
R5: the contents of R2 ## ## # # # # # #
R6: the contents of R3

and concluding
R1: the input program p p p p p p 1##
R2: an instruction number 1n 112 112 113 113 119
R3: the nth instruction of p 11##### 16 ###
R4: the contents of R1 1## 1## 1## 1## 1##
R5: the contents of R2
R6: the contents of R3
As promised, here are some words of explanation.

As you can see, there are four different colors of the columns. The colors indicate the sub-programs of u. The columns themselves indicate the register contents when one of the sub-programs begins.

The first color shown is orange. This is the the easiest to explain. The orange sub-program is 11#. So it adds a 1 to R2, indicating that at the very beginning of the execution of the input program, the instruction to look at first is instruction 1.

The beige columns alternate with the green ones. The purpose of the beige program is to take the input program (in R1) and the next instruction number (R2), and to look up the appropriate instruction and put it into R3. This is similar to a program which we saw earlier on. But we need to be sure that the contents of R1 and R2 are not destroyed at the end. (So you will probably need to use registers beyond R6 for all of this.) The way to understand the beige columns is that they tell the contents of the various registers at the beginning of the operation of the "beige sub-program". You will need to write that sub-program. It is a fairly straightforward modification of a program which you already have seen, the one that gives the nthe instruction of an input program. But there are some differences: you need to be sure that the output goes in R3, that the input is preserved, and that if the contents of R2 is one more than the length of the input program in R1, then the program "knows" about this and transfers over to the yellow sub-program shown at the end.

The main action of the steps is done in the green columns; more precisely, the columns shown are the beginnings of the "green" sub-program, and then the results of that sub-program are the beige columns which follow. The exact action depends on what kind of instruction is in R3 in the given green column. For example, if R3 has 11#, then in the next beige column we add a # to R5 (not R2: it is R5 that models what is in R2 of the real machine when we run program). We also must add 1 to R2 in simulating the execution of 11#, since after 11#, we go to the very next instruction. This is how the green columns work when we execute an instruction 11#. The other cases are left for you to think about. Note also that each time the green sub-program runs, R3 is emptied at the end.

The last column color is the yellow one at the very end. Before the yellow one starts up, the beige program has determined (in some sense) that our program p has 18 instructions and we have come to a point where we ask for instruction 19. Thus, the input program has halted. We therefore want to take the contents of R1 as run by the input program (this is the word in R4), and move this to R1. Also, we would like to clear out the contents of whichever registers are not empty. We do this so that the program we are writing will itself come to a good halt on its input.

It might seem silly to have R1 unchanged throughout. But this isn't really what is happening at all. In the course of the beige subprograms, parts of R1 are copied to other registers, and the copied back. So at the end of the beige sub-programs, we have the original program p back in R1.

Similarly, it might seem weird to have R6 completely unused in running a universal program on p. This is due to the fact that our program p only uses R1 and R2. If we worked with an example program that used R3, then R6 would not have remained empty in the tables.




Class project

Your project is to work in groups to write a universal program.

Probably you will want to follow the ideas above and to write the various sub-programs that were described. But you don't really have to follow the outline at all; you are free to depart from it. I will assume that you are following the ideas sketched out above. But again, you don't really have to do this as long as you explain what you are doing.

Here is what each group needs to do:

  1. Make a plan on how to divide up the work of writing the different sub-programs. The parts are not all equally hard. The beige program could be the hardest, especially if you follow my comment below on it.
  2. You will need to meet, or at least to email each other, so that you can be sure that the different sub-programs do what they are supposed to. You'll get started next time (Wednesday). I myself won't be in class that day, but your groups could/should get a start on the project.
  3. You also will need to have a plan on how to assemble everything together. The various sub-programs will need to "talk to each other" via goto statments. I can definitely help with ideas on joining programs. One good way is to use the Sanity parser. And one way that probably does not work well would be to simply put two flowcharts together.
  4. The group overall will need to turn in a program along with an explanation of the various parts. You should say clearly what the parts do, and also give some examples of how they run. If you have made flowcharts, it would be good to hand those in as well.
  5. You should test your overall program.
  6. At various points, you will be tempted to worry about what would happen if the input program does not halt. (For example, what should your program do if the input program is just 1111#### ?) The answer: we don't care what happens if the input program does not halt properly. You should not worry about this at all, only about the case when the input program really does halt.
  7. You are allowed to work with the simplifying assumption that the input program only uses R1, R2, and R3. You do not have to get a program u that woks on all input programs. But if you want a bigger challenge, you certainly may do the extra work!
  8. Your final draft should say who did what.
  9. The projects are due on October 10.
  10. It is important to write well. Your goal should be to write something that could be understood by someone else in the class.
  11. I would be happy to look at drafts or to talk about how things are going at any point. Hopefully this will not take so long, and hopefully you'll get started fairly soon.

A remark on the beige and green sub-programs

The way I have described things makes the green sub-programs a little harder than they have to be. That is, if we have an instruction in R3, say 111###, the first thing to do would seem to be to work with it in order to decide which kind of instruction it is. (In this case, the instruction is a transfer instruction, of course.) Now you certainly can write the green sub-program to start out by parsing the instruction in R3 and then working on a case-by-case basis. However, this is not the only way to do things. If you are careful with the beige program, the one that gives the nth instruction in the input program, then the parsing could be done automatically. What I mean here is that the beige program could be written in such a way that it incorporates the parsing as it goes.

If you are successful in getting a beige program that does what we want, then this would be much more work than all of the rest combined.




Coding all the registers in one

The program u that we have so far only works correctly for input programs that do all of their work on the first three registers. We now would like to drop this restriction and thereby get a better universal program.

As it happens, this takes a trick. The idea is to code all of the registers in a snapshot into one register. To make things concrete, suppose we want to code a register machine run at a particular time, and suppose that at that time the contents of the registers look as follows:

R1: 11# R2: R3: ## R4: R5: R6: 1 R7: # R8: ##1

(We understand also that all of the other registers are empty.) The first idea is probably to just code it by stacking the registers one after another, as in

11# ## 1 # ##1

But this will not work, since we have no way to know when the contents of any register is finished, or to tell that some of the registers are empty. So we need a better way. We can code in the following way:

the symbol 1 is coded by 11
the symbol # is coded by 1#
the end of a register is coded by ##
an empty register is therefore also coded by ##

Doing it this way allows us to code the eight registers, as in the table below:

Contents R1: 11# R2:     R3: ## R4: R5: R6: 1 R7: # R8: ##1
Encoded as 11111### ## R3:## ## ## 11## 1# ## 1#1#11##

Therefore we would encode the contents of these registers by the single word

11 11 1# ## ## 1# 1# ## ## ## 11 ## 1# ## 1# 1# 11 ##

What we want to do is to improve the universal program to work on arbitrary input programs. We start by changing the way that we use registers. From this point onward, we would like to do it according to the chart below:

We are going to use registers as follows:

R1: the input program p
R2: an instruction number 1n
R3: the nth instruction of p
R4: the contents of all regsiters, encoded as above

One basic problem that we face is that when we start the simulation of an input program, all of the registers are empty. So we have a few choices:

  1. We could process the input program in some way in order to see how many registers it actually uses. For example, if it used registers 1-5, we would then start with ## ## ## ## ## in R4.
  2. We could start with R4 empty, and then add to it as needed. For example, if the first instruction of the input program were 11#, we would write our program to make sure that R4 goes from being empty to having ## 1# ##.
Either of these alternatives would work fine. We chose to use the second way.


Implementing add# instructions

To see how some of this would work, we want to discuss how add1 instructions like 1##, 11##, etc. are implemented.

When we execute such a instruction, we'll assume as above that R4 contains the encoded contents of all the registers. We'll also assume that R5 contains a number in unary, call it m. We want a sub-program that will update R4 by adding 1# onto the end of the mth encoded register. Here is such a program:

11111##### 1### 1### 1### 1111##### 1111111111111111### 1111111### 111111## 1111##### 1### 1### 111111## 111111111111### 111111# 1111##### 1### 111### 111111## 11111111111111#### 111111# 1111111111111111#### 111111## 111111## 1### 11111##### 111111111### 1### 111111##### 111111111111111111111111#### 111### 1111111## 1111#### 1111111# 111111#### 111111##### 111111### 11111111### 111111##### 1### 1### 1### 1111111# 1111111## 111111111### 1111111# 111111##### 1### 111### 1111111## 111111111111111#### 1111111# 11111111111111111#### 1111111## 1111111## 1111 ##### 111111### 111### 1111111## 1111#### 1111111# 111111#### 1111111 ##### 111111### 111### 1111## 1111#### 1111# 111111####

You should try it out to make sure that it works right. Some good test cases would include the case when R4 is empty, as it would be in the beginning of a run.

So far, we have described how add# instructions would be implemented in a universal program. All of the same work goes for add1 instructions, of course, with just a few changes.

It would take a bit more work to handle the case instructions, but again, this is pretty similar.

Universal programs of more than one argument




Exercises


Exercise 1 What is φu(self)?

Incidentally, running u on self takes 22,376,608 steps, whereas running self on empty registers takes 3,322.


Exercise 2 Write a program trade which looks like it trades places with its input in R1. (Of course, a program cannot literally trade places with its input. But here is what we mean: running trade with p in R1 and all other registers empty does the same thing as running p with trade in R1 and all other registers empty.)

[Hint: You will need a universal program, and also an application of the Recursion Theorem.]

This exercise was given earlier, at the end of Lesson 4. But the solution really requires our work on universal programs.

My solution can be found here. To actually run this trade program on any inputs at all requires a lot of memory and speed: running it on 1#### too 9,124,755,237 instructions (over 9 billion).


Exercise 3 Write a program self1 which writes itself to R1 but only uses that register. That is, self1 does not use any register besides R1.

[Hint: you will need the technique of coding several registers into R1.]

Again, the solution will be fairly long. (Getting a solution less than 4,000 instructions long would be a good trick.)

My solution can be found here. Running that program self1 on itself took over 220 million instructions.



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