We looked at the idea of "primitive register machines" in the previous page. This page takes the ideas further and shows that primitive register machines can (in theory) compute a great deal.
The main omission to the primitive register machine language appears to be that there is no way of subtracting one from a register. What is needed is,
In fact, it is possible to program this using the existing instructions.
INPUT(x)
USES(y)
USES(z)
// does DECR(x) but without using the DECR command
LOOP(x) { INCR(y) } // make y the same as x
ZERO(x) // clear x
LOOP(y) { LOOP(z) { INCR(x) } ZERO(z) INCR(z) }
PRINT(x)
The point is that z is always 0 or 1, and is 0 the first time round the loop and 1 all other times, so INCR(x) is done times. Note too that DECR(x) should leave x the same if it started off being zero.
Sometimes, it is nice to be able to distinguish these two cases, i.e. to do "if x>0 then decrement x else do ..." This is provided with the following syntax.
Again, this is a convenience only because it is possible to program it in the original language.
INPUT(x)
USES(y)
INCR(y) // make y = 1
LOOP(x) { ZERO(y) } // make y = 0 if x is nonzero
DECR(x) // decrement x
LOOP(y) { ... } // do this once only if x was originally 0
Here are two more conveniences that are provided but which are not strictly necessary.
These can be programmed using the same trick. You can also do IFNZ(x) { ... } ELSE { ... } and IFNZ(x) { ... } ELSE { ... } if you want to do two different things based on whether a register is zero or not.
There is one group of instructions that can be used that cannot by programmed with the existing instructions. These are,
BREAK is normally put inside an IF or ELSE clause: the following are commonly used and provided as conveniences.
Not every program written using these extra instructions can be written without them. This is an interestng mathematical theorem about programming. It is not easy to prove statments like this in general. If you really want details, the best known example is a function called the "Ackermann function". This can be programmed using INFLOOP and BREAK but (it can be proved) cannot be programmed without these.
Here is an example that uses INFLOOP and BREAK for convenience, but could in fact have been written without INFLOOP. It computes the next prime number greater than the input x.
INPUT(x)
// replaces x with the smallest prime greater than x
// sets y=1 if x is prime, y=0 otherwise
// keeps y=1 if d does not divide x, else sets y=0
INCR(x)
INFLOOP {
USES(y)
USES(z) // loop variable
USES(d) // test divisor
ZERO(y)
INCR(y) // prepare y = 1 for "true" answer
LOOP(x) { INCR(z) }
DECR(z) // z is now x-1
DECR(z) ELSE { ZERO(y) } // z = max(0,x-2), y=0 in case x=0 or 1
INCR(d)
INCR(d) // d = 2, first divisor to test
LOOP(z) {
USES(u)
USES(v)
ZERO(y)
LOOP(x) { INCR(v) } DECR(v) // set v = x-1
LOOP(d) { INCR(u) } DECR(u) // set u = d-1
INFLOOP {
LOOP(u) {
// if v is zero here then d does not divide x
DECR(v) ELSE { INCR(y) BREAK }
}
// if v is zero finished
DECR(v) ELSE { BREAK }
}
BREAKIFZ(y) // y=0 means not a prime
INCR(d)
}
// if y>0 we have found a prime
BREAKIFNZ(y)
// else increment x and try again
INCR(x)
}
PRINT(x)
Click the comments to expand or contract the various sections. You can download this program here. (Right click the link and save as...)
This is a bit longer and more complicated than anything you've seen yet. Some students will enjoy studying it and seeing how it works, and possibly improving it. Others can simply look at it and try it out. But it's nice just to know that something like this is possible. If you want to try to understand it I suggest you look at the outermost loop first. You can ignore most of the content of the loop, just look at the comments that says what the code does. Assume it works correctly and then understand why that means the whole program works. When you are happy with this, try to understand the details of this loop, but ignore the content of the inner loops for now. And so on.
I used infinite loops in the "prime" example because that was most convenient. In this particular case the infinite loops can be avoided by first calculating a maximum number of times each loop will have to go. (For example, Bertrand's Postulate says that for all there is a prime between and , so the outer infinite loop only has to go at most x times.) Note, however, that if we were to search for prime pairs in the same way no known theorem would allow us to do this without infinite loops. I suspect it is an open question whether prime pairs could be searched for without infinite loops.
Exercise: suppose there are only finitely many prime pairs. Then there is a register machine program without infinite loops that computes the least prime pair greater than its input, or zero if there is no such prime pair.
This page has looked into more detail about how it is possible to program register machines to do many more kinds of calculations. For the purposes of the 2NP module it is useful simply because it provides many more examples and a chance to practise and develop programming skills using these very simple machines.
Readers who like the idea of very simple machines being able to compute remarkably complicated things will be interested in the subject of "Computability Theory" (also called "Recursion Theory") which is a branch of mathematical logic. One very elegant way to start this subject is to study what can and can't be computed by register machines. It turns out that primitive register machines can compute precisely the primitive recursive functions (a natural class of functions that can be defined in many different ways) and general register machines with "infinite loops" can compute any function at all that is computable by any other of the standard models of computation (such as "Turing Machine", "Lambda Calculus" etc.) One possible place to find out about this is Nigel Cutland's book "Computability" (C.U.P.) which uses the approach using an idea of register machines very similar to mine.
However, this takes us beyond the current course. There are two more important pages on mathematical background and examples, but after those the next main topic is to explain how the C++ language works, and we'll start by explaining how to re-write register machine programs in C++.