Universal Register Machine

1. Gadgets

A gadget is a partial register machine graph.

• It has one entry wire, and one or more exit wires.
• The gadget operates on input and ouptut registers specified in the gadget's name.
• The gadget may use other registers, called scratch registers, for temporary storage.
• The gadget assumes scratch registers are initialized to .
• The gadget ensures scratch registers are set back to before the gadget exits.

1.1 Zero

An example gadget is the "zero " gadget:

1.2 Addition

Another gadget is the "add to " gadget:

1.3 Copy

Another gadget is the copy to gadget:

Another gadget is "copy to and " gadget:

1.4 Multiply

Another gadget is "muliply by to " gadget:

1.5 Push

Another gadget is "push to stack " gadget:

Given input values , and , it returns the output values , and .

1.6 Pop

Another gadget is "pop to " gadget:

If , then return and go to "empty". If , then return and and go to "done".

2. Universal Register Machine

The universal register machine carries out the following computations:

• Starts with , (code of the program), (code of a list of arguments), and all other registers zeroed.
• Decode as an RM program .
• Decode as a list of register values .
• Carry out the computation of starting with , , , (and any other registers zeroed).

Mnemonics for the registers of (Universal Register Machine) and the role they play:

1. : result of the simulated computation (if any).
2. : code of the program.
3. : code of a list of arguments.
4. : PC (program counter) - label of the current instruction._
5. : - label number of the next instruction(s).
6. : - code of the current instruction body.
7. : - value of the register to be used by the current instruction.
8. : scratch registers.
9. : other scratch registers.

Execution runs as follows:

1. Copy the th item of into (halt if > length of list.)
2. If , halt. Otherwise, decode . is either or .
3. Copy the th item of into .
4. Execute instruction at , update , restore register values at .
5. Repeat