Register Machines

Why Registers?

Tape-based automata are quite minimalistic, and great for making a theory from just about the most primitive concepts. But registers can also serve as the basis of automata theory, even though they feel a little higher-level.

And also, let’s face it, real machines have registers.

The Basics

In automata theory, A register machine has (indexable) registers $r_0, r_1, r_2, \ldots$, each holding a single natural number. The machine’s control is a program, defined as a list of instructions. The instructions are normally executed in sequence, but some instructions can cause a “jump” to an arbitrary instruction. The instruction set varies from model to model (of which there exist an infinite number of possibilities).

       ┌────────────────────┐
    r0 │                    │
       ├────────────────────┤
    r1 │                    │
       ├────────────────────┤
    r2 │                    │
       ├────────────────────┤
    r3 │                    │
       ├────────────────────┤
    r4 │                    │
       ├────────────────────┤
             .   .   .

Don’t miss the Wikipedia article on register machines.

The simplest kind of register machines are those whose instruction set only allows registers to be incremented or decremented only. These are called counter machines.

Counter Machines

Here’s a sample instruction set (I just made it up) for a counter machine:

This instruction set is pretty simple; it assumes the input is the contents of the registers before execution, and the output is the contents of $r_0$. The program is a list of instructions and the program ends when there are no more instructions to execute. (That is, the you executed the last instruction which was not a jump, or you jumped to a location outside the program.)

For convenience, we can also imagine a machine that has separate streams for input and output, operated on by $\textsf{read}$ and $\textsf{write}$ instructions, respectively. We might even throw in a convenient instruction to halt the program:

Because counter machine programs are primitive, like Turing Machines, programs are pretty long. Here’s a program that reads two integers, adds them, and writes their sum.

read r0            // x
read r1            // y
jzdec r1, 3        // if y is 0, our answer is in r0
inc r0             // x++
jump -2            // loop back
write r0           // there's the output

If you have a sufficient set of instructions, you can show a register machine to be equivalent in computing power to a Turing machine.

Surprisingly, there exists a register machine that is equivalent in computing power to a Turing Machine that has only two instructions:

O RLY?

Remember the reads and writes aren’t actually needed. You can still compute by having a convention such that the input of the program starts in register 0 and the output is read from register 1 whenever there are no more instructions to execute. Since each register is an unbounded integer, it can encode whatever the heck you like.

RAMs

A more sophisticated type of register machine is the RAM (Random Access Machine). Instruction sets vary, but usually contain arithmetic, logic, and jumps.

Three Address Machines (3AC)

It is common to allow instructions to have up to 3 operands. Such an instruction set is called a 3AC, for “three-address code” and might look like this:

Now we can improve the model a great deal by adding two powerful ideas: (1) we can let our source operands be constant values (also known as immediate values), and (2) we can get the register index from the contents of another register (known as an indirect address). For example:

copy r8, 5        // with immediate operands, no need for LOAD
copy r5, 13
copy r2, r8       // copy contents of r8 into r2
copy r2, *r8      // copy contents of r5 into r2 (bc r8 holds 5)
copy *r2, r8      // copy contents of r8 into r13 (bc r2 holds 13)
copy *r2, *r8     // copy contents of r5 into r13
neg r3, *r2       // copy negation of r13 into r3
add r3, *r8, 5
sub *r2, r13, *r13

Notice that sources can be immediate, direct register, or indirect register; destinations can be direct or indirect register (not immediate!).

Let’s now compose a more expressive machine instruction set:

Here is a GCD program on this machine:

// while y != 0:
//   x, y = y, x % y
// print(x)

read r0            // x
read r1            // y
jz r1, 5           // if y is 0, we're done
copy r2, r1        // old_y <- y (to "save" it)
mod r1, r0, r2     // y <- x % y
copy r0, r2        // x <- old_y
jump -4            // back to top of "loop"
write r0

For convenience, we can use labels. Labels are just a shorthand, they are not different instructions or anything. They just make things easier for humans to understand. We are not changing the machines:

// while y != 0:
//   x, y = y, x % y
// print(x)

  read r0            // x will be in r0
  read r1            // y will be in r1
start:
  jz r1, wrapup      // if y is 0, we're done
  copy r2, r1        // old_y <- y (to "save" it)
  mod r1, r0, r2     // y <- x % y
  copy r0, r2        // x <- old_y
  jump start         // back to top of "loop"
wrapup:
  write r0           // print x

Two Address Machines (2AC)

If we restrict the target of the arithmetic and logic operations to be one of the sources, our instructions now have at most only two operands:

Code gets a little longer now:

// 2AC GCD PROGRAM

// while y != 0:
//   x, y = y, x % y
// print(x)

  read r0            // x will be in r0
  read r1            // y will be in r1
start:
  jz r1, wrapup      // if y is 0, we're done
  copy r2, r0        // old_x <- x
  copy r3, r1        // old_y <- y
  mod r2, r3         // old_x % old_y
  copy r1, r2        // new y for next iteration
  copy r0, r3        // new x for next iteration
  jump start         // back to top of "loop"
wrapup:
  write r0           // print x

One Address Machines (1AC)

We can even make the target register always be implicitly $r_0$, which, since this is always the destination for all the arithmetic operations, we call the accumulator, and we now have at most one operand per instruction:

Programs start to get a lot longer with this architecture:

// 1AC GCD PROGRAM

// while y != 0:
//   x, y = y, x % y
// print(x)

  read            // x in r0
  store r1        // x in r1
  read            // y in r0
start:
  jz wrapup       // if y is 0, we're done
  store r2        // old_y saved in r2
  load r1         // x in r0
  store r3        // old_x saved in r3
  mod r2          // x % y in r0
  store r1        // new x for next iteration
  load r2         // new y for next iteration
  jump start      // back to top of "loop"
wrapup:
  load r1        // Now x is in r0
  write          // So we can write x

Stack Machines (0AC)

We can make all the operands implicit (except of course for loads and jumps) if we just organize all our registers like a stack:

Stack machines are cool when executing arithmetic expressions. Work left to right. Example:

// Stack machine code for 7 - 3 * 8 ** 1 / 3

load 7    // 7
load 3    // 7 3
load 8    // 7 3 8
load 1    // 7 3 8 1
pow       // 7 3 (8**1)
mul       // 7 (3*(8**1))
load 3    // 7 (3*(8**1)) 3
div       // 7 ((3*(8**1))/3)
sub       // 7-((3*(8**1))/3)

Fun fact: if all we had was a single stack, we would not have the power of a Turing Machine. But if we add a separate stash of random access storage location for variables, we’re good. Example time:

// 0AC GCD PROGRAM

// while y != 0:
//   x, y = y, x % y
// print(x)

// Assuming separate stash of labeled registers for storage,
// BUT all operations can only occur on stack top.
// STORE instruction does a pop.

  read
  store x
  read
  store y
start:
  load y
  jz wrapup       // if y is 0, we're done
  load x
  load y
  store x         // new x is the old y
  load y
  mod             // x % y
  store y         // new y is x % y
  jump start      // back to top of "loop"
wrapup:
  load x
  write

RASPs

Another kind is called the RASP (Random Access Stored Program). The basic idea is that the program itself is stored in the registers, encoded just like data. In theoretical terms that we’ve heard previously,

• RAMs are like typical Turing Machines; RASPs are like Universal Turing Machines.
• RAMs have a Harvard architecture; RASPs have a von Neumann architecture.

Example time! We’ll make a trivial RASP machine based off the 1AC machine above. Each instruction will take up two registers: the first with an instruction code and the second for the operand. We’ll begin with an actual machine, then generalize it to describe the model:

56  6  0  0  0  0 92  0
 5  2 92  0  5  3  1  3
64 32  5  4  1  2 25  4
 5  3  1  4  5  2 56 14
 1  2 92  1

The instruction codes are as follows:

There are four codes for each “instruction” because the last two bits of the instruction specify the addressing mode: 00=immediate, 01=register, 10=register_indirect, 11=accumulator. The one exception is the unary instruction, which does not use addressing modes; instead the operand word is 0=read, 1=write, 2=neg, 3=not. Any instruction code not in the table above is considered a halt instruction.

When we write the program above using mnemonics, we get:

// RASP GCD PROGRAM
// while y != 0:
//   x, y = y, x % y
// print(x)

00: jump 6              // skip over data registers
02: (space for x)
03: (space for y)
04: (space for old_y)
05: (unused)
06: read
08: store r2            // x in r2
10: read
12: store r3            // y in r3
14: load r3             // also label start is here
16: jz 32               // if y is 0, we're done
18: store r4            // old_y in r4
20: load r2             // x
22: rem r4              // x % y
24: store r3            // new y for next iteration
26: load r4             // old_y
28: store r2            // new x for next iteration
30: jump 14             // back to top of "loop"
32: load r2             // x in accumulator
34: write               // print x

The RASP model is generally the foundation for real machines. But not exactly, of course, as the RASP is idealized in having an unbounded number of registers holding unbounded values. Real machines, because they have to be physical devices, make certain simplifications:

• Instead of treating all “memory” as registers, a real machine has a small number of registers in which arithmetic and logic are done, and a few levels of memory for storing and retrieving data. This “memory” comes in main flavors: main memory, various levels of cache memory, and even external storage. (While there is technically a finite amount of memory available in the universe as we know it, in theory one could, as long as you could afford it, keep purchasing enough storage space for one’s needs.)
• The registers and memory cells are bounded to a certain number of bits.

Read more about RASPs at Wikipedia.

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What are the three major differences between the register machine model and the tape model used in Turing Machines?
   (1) Registers hold natural numbers directly, while tape cells each hold a single symbol from a finite alphabet, (2) Registers are accessed by index, while tape access is done by moving one cell at a time, (3) Register machine control is a list of instructions, while Turing machine control uses state transitions.
2. What is a counter machine?
   A type of register machine whose instruction set only allows registers to be incremented or decremented.
3. There is a famous two-instruction counter machine that is Turing-complete. What are its two instructions?
   inc and jzdec
4. Where are inputs and outputs to a register machine typically defined?
   Either (1) in designated input/output registers or (2) in separate input and output streams accessed via read and write instructions.
5. What is a 3AC instruction set?
   An instruction set where binary arithmetic and logic instructions have three operands: a destination and two sources.
6. What is a 2AC instruction set?
   An instruction set where binary arithmetic and logic instructions have two operands: a destination (which is also one of the sources) and another source.
7. What is a 1AC instruction set?
   An instruction set where binary arithmetic and logic instructions have one operand: a source. The destination is always an implicit accumulator register.
8. What is a 0AC instruction set?
   An instruction set where all arithmetic and logic operations have no operands; they operate on the top of a stack.
9. What does a stack machine program to compute 5 * 2 + 8 / 8 look like?

   // Stack machine code for 5 * 2 + 8 / 8
   load 5    // 5
   load 2    // 5 2
   mul       // 10
   load 8    // 10 8
   load 8    // 10 8 8
   div       // 10 1
   add       // 11
   

10. What does a 1AC program to compute 5 * 2 + 8 / 8 look like?

    // 1AC code for 5 * 2 + 8 / 8
    load 5
    mul 2       // r0 = 5 * 2
    store r1    // r1 = 10
    load 8
    div 8       // r0 = 8 / 8
    add r1      // r0 = 10 + 1
    

11. What does a 2AC program to compute 5 * 2 + 8 / 8 look like?

    copy r0, 5
    mul r0, 2       // r0 = 5 * 2
    copy r1, 8
    div r1, 8       // r1 = 8 / 8
    add r0, r1      // r0 = 10 + 1
    

12. What does a 3AC program to compute 5 * 2 + 8 / 8 look like?

    mul r0, 5, 2       // r0 = 5 * 2
    div r1, 8, 8       // r1 = 8 / 8
    add r0, r0, r1     // r0 = 10 + 1
    

13. What is the difference between a RAM and a RASP?
    A RAM has a separate program and data memory, while a RASP stores both program instructions and data in the same memory.
14. A RAM has a ________________ architecture and a RASP has a ________________ architecture.
    Harvard; von Neumann
15. What kind of Turing Machine vibes does a RASP give off?
    Universal

Summary