Register Machines

Tape-based automata, like the Turing Machine, are not the only formal models of computation studied in computer science.

Why Registers?

Tape-based automata are quite minimalistic, and great for making a theory from just about the most primitive concepts. Registers feel a little higher-level, and also, let’s face it, real machines have registers.

The Basics

In automata theory, A register machine has a number of registers $r_0, r_1, r_2, \ldots$, each holding a single (unbounded) natural number. The machine’s control is a program, defined as a list of (labeled) 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:

Various Counter Machine Instructions
$\textsf{clear }r_i$$r_i := 0$
$\textsf{inc }r_i$Increment the contents of $r_i$
$\textsf{dec }r_i$Decrement the contents of $r_i$
$\textsf{copy }r_i, r_j$copy contents of $r_j$ into $r_i$
$\textsf{jz } r_i, n$Jump ahead (or back, if $n$ is negative) $n$ instructions if contents of $r_i$ is $0$
$\textsf{je } r_i, r_j, n$Jump ahead (or back, if $n$ is negative) $n$ instructions if contents of $r_i$ is equal to the contents of $r_j$
$\textsf{jzdec }r_i, L$If the contents of $r_i$ is $0$ then jump $n$ instructions, else decrement the contents of $r_i$
$\textsf{jump } n$Jump ahead (or back, if $n$ is negative) $n$ instructions

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 you have no more instructions.

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:

More Instructions
$\textsf{read }r_i$Consume next value from input stream and store in $r_i$
$\textsf{write }r_i$Append contents of $r_i$ to output stream
$\textsf{halt}$Stop executing

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, we're done
inc r0             // x++
jump -2            // loop back
write r0           // there's the output

If you have the right 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:

Simplest Counter Machine
$\textsf{inc }r_i$Increment the contents of $r_i$
$\textsf{jzdec }r_i, L$If the contents of $r_i$ is $0$ then jump $n$ instructions, else decrement the contents of $r_i$
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. Some instruction sets feature three-operands (sometimes called 3AC sets) and might look like this:

Restricted 3AC: Simple Direct Addressing Only
InstructionDescription
$\textsf{load } r_k, n$$r_k := n$
$\textsf{copy }r_i, r_j$copy contents of $r_j$ into $r_i$
$\textsf{add } r_i, r_j, r_k$Store sum of contents of $r_j$ and $r_k$ into $r_i$
... and so on for $\textsf{sub}$, $\textsf{mul}$, $\textsf{div}$, $\textsf{pow}$, $\textsf{and}$, $\textsf{or}$, $\textsf{lt}$, $\textsf{le}$, $\textsf{eq}$, $\textsf{ne}$, $\textsf{ge}$, $\textsf{gt}$, $\textsf{shl}$, $\textsf{shr}$, and any other binary operation you can think of
$\textsf{neg } r_i, r_j$Store negation of the contents of $r_j$ into $r_i$
$\textsf{not } r_i, r_j$Store bitwise negation of the contents of $r_j$ into $r_i$
... and so on for any other unary operation you can think of
$\textsf{jump } n$Jump ahead (or back, if $n$ is negative) $n$ instructions
$\textsf{jz } r_i, n$Jump ahead (or back, if $n$ is negative) $n$ instructions if contents of $r_i$ is $0$
... and any of the jump, read, write, and halt instructions from above

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) let our registers be indirect. For example:

copy r8, 5     -- with imm 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
copy *r2, r8   -- copy contents of r8 into r13
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

Now sources can be immediates, direct registers, or indirect registers; destinations can be direct or indirect registers (not immediates!). So we can write:

3AC
InstructionDescription
$\textsf{copy }dest, src$$\langle dest \rangle := \langle src \rangle$
$\textsf{add }dest, src_1, src_2$$\langle dest \rangle := \langle src_1 \rangle + \langle src_2 \rangle$
$\textsf{sub }dest, src_1, src_2$$\langle dest \rangle := \langle src_1 \rangle - \langle src_2 \rangle$
... and so on for MUL, DIV, POW, AND, OR, LT, LE, EQ, NE, GE, GT, SHL, SHR
$\textsf{neg }dest, src$$\langle dest \rangle := - \langle src \rangle$
$\textsf{not }dest, src$$\langle dest \rangle := \neg \langle src \rangle$
$\textsf{jz }src, L$If $\langle src \rangle = 0$ then jump to $L$
$\textsf{je }src_1, src_2, L$If $\langle src_1 \rangle = \langle src_2 \rangle$ then jump to $L$
$\textsf{jump } L$Jump to instruction at address $L$
$\textsf{read }dest$$\langle dest \rangle := $ next value from input stream
$\textsf{write }src$Append $\langle src \rangle$ to output stream
$\textsf{halt}$Stop executing

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

Another variation requires the target to be one of the sources:

2AC
InstructionDescription
$\textsf{copy }dest, src$$\langle dest \rangle := \langle src \rangle$
$\textsf{add }dest, src$$\langle dest \rangle := \langle dest \rangle + \langle src \rangle$
$\textsf{sub }dest, src$$\langle dest \rangle := \langle dest \rangle - \langle src \rangle$
... and so on for other binary operations
$\textsf{neg }dest$$\langle dest \rangle := - \langle dest \rangle$
$\textsf{not }dest$$\langle dest \rangle := \neg \langle dest \rangle$
... and so on for other unary operations
$\textsf{jz }src, L$If $\langle src \rangle = 0$ then jump to $L$
$\textsf{jump } L$Jump to instruction at address $L$
$\textsf{read }dest$$\langle dest \rangle := $ next value from input stream
$\textsf{write }src$Append $\langle src \rangle$ to output stream
$\textsf{halt}$Stop executing

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

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:

1AC (Accumulator Machine)
InstructionDescription
$\textsf{load }src$$r_0 := \langle src \rangle$
$\textsf{store }dest$$\langle dest \rangle := \langle r_0\rangle$
$\textsf{add }src$$r_0 := \langle r_0\rangle + \langle src \rangle$
$\textsf{sub }src$$r_0 := \langle r_0\rangle - \langle src \rangle$
... and so on for other binary operations
$\textsf{neg }$$r_0 := - \langle r_0\rangle$
$\textsf{not }$$r_0 := \neg \langle r_0\rangle$
... and so on for other unary operations
$\textsf{jz }L$If $\langle r_0\rangle = 0$ then jump to $L$
$\textsf{jump } L$Jump to instruction at address $L$
$\textsf{read }$$r_0 := $ next value from input stream
$\textsf{write }$Append $\langle r_0\rangle$ to output stream
$\textsf{halt}$Stop executing

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

We can make all the arguments implicit if we just organize all our registers like a stack:

0AC (Stack Machine)
InstructionDescription
$\textsf{load } n$Push $n$
$\textsf{add}$Pop into $y$; pop into $x$; push $x + y$
$\textsf{sub}$Pop into $y$; pop into $x$; push $x - y$
... and so on for other binary operations
$\textsf{neg}$Pop into $x$; push $-x$
$\textsf{not}$Pop into $x$; push $\neg x$
... and so on for other unary operations
$\textsf{jz } L$Pop into $x$; If $x= 0$ jump to instruction at address $L$
$\textsf{jump } L$Jump to instruction at address $L$
$\textsf{halt}$Stop executing

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)

To be able to move things around with a stack architecture, we can add DUP and SWAP instructions, or even have a separate stash of labeled registers for storage.

// 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). Read the Wikipedia article for this one.

Exercise: What is the historical importance of the RASP model? Why was it created?

Summary

We’ve covered:

  • What register machines are and why they are interesting
  • Counter machines
  • The simplest counter machine that is Turing equivalent
  • 3AC RAMs
  • 2AC RAMs
  • 1AC RAMs (accumulator machines)
  • 0AC RAMs (stack machines)
  • RASPs