What is an Unlimited Register Machine?
A small note to the reader:
There are different versions of an unlimited register machine with slight technical distinctions, but they all are the same in principle. The one we will cover is discussed by Nigel J. Cutland in his book called Computability: An Introduction to Recursive Function Theory1. It is specifically adapted for his book to teach computability theory. Cutland has based his own modified definition on the prior work of Shepherdson and Sturgis in 1963 2.
N.J. Cutland’s URM
Cutland describes an unlimited register machine (URM) as an “[idealized] computer that operates on programs” (9). Furthermore, paraphrasing, on page 9: A URM works on a specific set of instructions; a list (a sequential ordering) of these instructions is called a program.
Some of the definitions and assumptions seem trivial, but it is important to be explicit and leave nothing to ambiguity, so we can create formal theorems and reason about them. Fundamentally, few would require an explanation of what a program is as it has become a colloquial term due to how ubiquitous computers are today.
Continuing, there is no ambiguity in the meaning of these instructions as they are exact, well defined, and specified. We shall see the instructions soon. Cutland wants us to understand that instructions are the mechanical steps such that they can be executed automatically without any thought or intelligence. In fact, Cutland spends some time making sure that the reader understands that “their implementation requires no ingenuity or even intelligence beyond that needed to obey the … instructions.” (7) Lastly, this machine operates only on natural numbers. This restriction is important for the definition as the model is used to make certain theorems about computation in general.
This machine does not need to exist in a physical sense; with a pen and paper we can work out the result of a program if we chose to by following the instructions to the letter. Register machines conceptually model modern computers in an abstract high-level sense. It is true that modern machines do not have unlimited registers and unlimited memory, but we make that assumption anyway. It just means we are free to use as much memory as needed. If a modern machine requires more memory, we can add more memory.
In all practical sense, all the programs need to be finite in themselves; we cannot have an infinite program because there is no way to encompass a meaning of one. Cutland writes, “the programs for our machine will be finite, and we will require that a completed computation only takes a finite number of steps” (9); this restriction does not exclude extremely large programs and programs requiring extremely large number of registers.
A URM consists of infinite number of registers which are labeled as $R_1$, $R_2$, $R_3$, … $R_4$, and each register contains at most one natural number (7). Registers are just places that store one arbitrary large natural number. Registers can be referred to by their label. We can visualize the state of the machine by taking a snapshot like in the example below:
| $R_1$ | $R_2$ | $R_3$ | $R_4$ | … | $R_n$ |
|---|---|---|---|---|---|
| $r_1$ | $r_2$ | $r_3$ | $r_4$ | … | $r_n$ |
| Line # | Instruction |
|---|---|
| 1 | Instruction |
| 2 | Instruction |
| . | . |
| $i$ | Instruction |
| . | . |
| $n-1$ | Instruction |
| $n$ | Instruction |
| Instruction |
|---|
| Line # $i$ |
The top number is the register number ($R_n$) and the bottom one is the register value ($r_n$). A snapshot is a frozen state of a machine at some point in time. A state consists of all register values, the program, and the current instruction that is being executed. Some literature calls this a machine configuration. This is the only concept of memory in the definition of an URM and, hence, the register in an unlimited register machine.
Simple instructions operate on these registers. Cutland’s URM has four instructions (12):
| Instruction Name | Instruction Syntax | Effect |
|---|---|---|
| Zero | $Z(n)$ | $R_n$ ← $0$ |
| Successor | $S(n)$ | $R_n$ ← $R_n+1$ |
| Transfer | $T(m,n)$ | $R_n$ ← $R_m$ |
| Jump | $J(m,n,q)$ | if $(R_m$=$R_n)$ then jump to instruction/line q; otherwise proceed to the next instruction |
Let us explain verbosely in plain English the above:
- A zero instruction clears out a register; clearing means we assign zero to $R_n$.
- A successor instruction increments a register by one; the name successor is not arbitrary and literally means the next possible number after the previous number. This is important as it mirrors mathematical induction.
- A transfer instruction assigns one register’s value to another register’s value;
- A jump is a branching instruction which splits the current execution flow in two possible directions. If the specified registers are equal ($R_m$ and $R_n$), the program will proceed to an instruction at location q (usually a line number); otherwise, the registers ($R_m$ and $R_n$) are not equal, and the program will proceed to the next instruction by default. Basically, this is how this machine does a conditional statement. This is an if-statement in programming languages.
if(Rm == Rn)
Do this branch
else
Do this branch
All instructions execute in a sequential order and only a branch instruction in a URM is responsible for changing the control flow of the program. All programs begin with the first line.
To build other functions, like addition and multiplication, we must use the instructions above. It is good news that the four instructions above can build any and all functions needed to compute almost anything of use. How do we know this? Well, that is the study of computability theory and the rest of Cutland’s book and much more.
Remember we are discussing the feasibility and not efficiency of instructions and functions. A native addition instruction adding two numbers might be useful but in this URM model we need to build it using the primitives above.
Lastly, we can set the initial input of the machine’s starting state by putting the numbers into the registers directly, or we may have a program contain the initial values of the registers by executing an instruction to increase certain registers. Cutland calls this the “initial configuration” (11).
For example, we can put 5 into register 1 or we can have a program increment register 1, five times. We can formalize a program as a list $P = I_1, I_2, I_3, … ,I_n$. The program stops or halts when there are no more instructions left to execute or we have reached the end of a program. The caveat here is that we are assuming that the program will halt, which may not necessarily be true, and we allow that.
URM simulators
Check out my project for an Unlimited Register Machine, where you can run any and all URM programs using the four instructions above.
Some other excellent simulators to try:
- http://sites.oxy.edu/rnaimi/home/URMsim.htm
- https://www.math.ucla.edu/~bonsoon/urm.html
- https://sean.mcgivern.me.uk/urm-evaluator/
So go on ahead and give them a try.
Notes
- The original link at https://www.math.ucla.edu/~bonsoon/urm.html is no longer available.
- An archived version can be found here: https://web.archive.org/web/20211204143722/https://www.math.ucla.edu/~bonsoon/urm.html
Bibliography
Cutland, N.J. Computability: An introduction to Recursive Function Theory. Cambridge (United Kingdom), Cambridge University Press, 1980.