Register Machine - Formal Definition

Formal Definition

No standard terminology exists; each author is responsible for defining in prose the meanings of their mnemonics or symbols. Many authors use a "register-transfer"-like symbolism to explain the actions of their models, but again they are responsible for defining its syntax.

A register machine consists of:

1. An unbounded number of labeled, discrete, unbounded registers unbounded in extent (capacity): a finite (or infinite in some models) set of registers each considered to be of infinite extent and each of which holds a single non-negative integer (0, 1, 2, ...). The registers may do their own arithmetic, or there may be one or more special registers that do the arithmetic e.g. an "accumulator" and/or "address register". See also Random access machine.
2. Tally counters or marks: discrete, indistinguishable objects or marks of only one sort suitable for the model. In the most-reduced counter machine model, per each arithmetic operation only one object/mark is either added to or removed from its location/tape. In some counter machine models (e.g. Melzak (1961), Minsky (1961)) and most RAM and RASP models more than one object/mark can be added or removed in one operation with "addition" and usually "subtraction"; sometimes with "multiplication" and/or "division". Some models have control operations such as "copy" (variously: "move", "load", "store") that move "clumps" of objects/marks from register to register in one action.
3. A (very) limited set of instructions: the instructions tend to divide into two classes: arithmetic and control. The instructions are drawn from the two classes to form "instruction-sets", such that an instruction set must allow the model to be Turing equivalent (it must be able to compute any partial recursive function).
   1. Arithmetic: arithmetic instructions may operate on all registers or on just a special register (e.g. accumulator). They are usually chosen from the following sets (but exceptions abound):
      • Counter machine: { Increment (r), Decrement (r), Clear-to-zero (r) }
      • Reduced RAM, RASP: { Increment (r), Decrement (r), Clear-to-zero (r), Load-immediate-constant k, Add (r₁,r₂), proper-Subtract (r₁,r₂), Increment accumulator, Decrement accumulator, Clear accumulator, Add to accumulator contents of register r, proper-Subtract from accumulator contents of register r, }
      • Augmented RAM, RASP: All of the reduced instructions plus: { Multiply, Divide, various Boolean bit-wise (left-shift, bit test, etc.)}
   2. Control:
      • Counter machine models: optional { Copy (r₁,r₂) }
      • RAM and RASP models: most have { Copy (r₁,r₂) }, or { Load Accumulator from r, Store accumulator into r, Load Accumulator with immediate constant }
      • All models: at least one conditional "jump" (branch, goto) following test of a register e.g. { Jump-if-zero, Jump-if-not-zero (i.e. Jump-if-positive), Jump-if-equal, Jump-if-not equal }
      • All models optional: { unconditional program jump (goto) }
   3. Register-addressing method:
      • Counter machine: no indirect addressing, immediate operands possible in highly atomized models
      • RAM and RASP: indirect addressing available, immediate operands typical
   4. Input-output: optional in all models
4. State register: A special Instruction Register "IR", finite and separate from the registers above, stores the current instruction to be executed and its address in the TABLE of instructions; this register and its TABLE is located in the finite state machine.
   • The IR is off-limits to all models. In the case of the RAM and RASP, for purposes of determining the "address" of a register, the model can select either (i) in the case of direct addressing—the address specified by the TABLE and temporarily located in the IR or (ii) in the case of indirect addressing—the contents of the register specified by the IR's instruction.
   • The IR is not the "program counter" (PC) of the RASP (or conventional computer). The PC is just another register similar to an accumulator, but dedicated to holding the number of the RASP's current register-based instruction. Thus a RASP has two "instruction/program" registers—(i) the IR (finite state machine's Instruction Register), and (ii) a PC (Program Counter) for the program located in the registers. (As well as a register dedicated to "the PC", a RASP may dedicate another register to "the Program-Instruction Register" (going by any number of names such as "PIR, "IR", "PR", etc.)
5. List of labeled instructions, usually in sequential order: A finite list of instructions . In the case of the counter machine, random access machine (RAM) and pointer machine the instruction store is in the "TABLE" of the finite state machine; thus these models are example of the Harvard architecture. In the case of the RASP the program store is in the registers; thus this is an example of the von Neumann architecture. See also Random access machine and Random access stored program machine.
   Usually, like computer programs, the instructions are listed in sequential order; unless a jump is successful the default sequence continues in numerical order. An exception to this is the abacus (Lambek (1961), Minsky (1961)) counter machine models—every instruction has at least one "next" instruction identifier "z", and the conditional branch has two.
   • Observe also that the abacus model combines two instructions, JZ then DEC: e.g. { INC ( r, z ), JZDEC ( r, z_true, z_false ) }.
     See McCarthy Formalism for more about the conditional expression "IF r=0 THEN z_true ELSE z_false" (cf McCarthy (1960)).