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.
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.
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.
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 | |
|---|---|
| Instruction | Description |
| $\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 | |
|---|---|
| Instruction | Description |
| $\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 | |
|---|---|
| Instruction | Description |
| $\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) | |
|---|---|
| Instruction | Description |
| $\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) | |
|---|---|
| Instruction | Description |
| $\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
Another kind is called the RASP (Random Access Stored Program). Read the Wikipedia article for this one.
We’ve covered: