Editing Register machine (section)

== Formal definition ==
A register machine consists of:

#'''An unbounded number of labelled, discrete, unbounded registers unbounded in extent (capacity)''': a finite (or infinite in some models) set of registers <math>r_0 \ldots r_n</math> each considered to be of infinite extent and each holding a single non-negative integer (0, 1, 2, ...).<ref group="nb" name="NB1"/> 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]].''
#'''Tally counters or marks''':<ref group="nb" name="NB2"/> 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,<ref name="Melzak_1961"/> Minsky<ref name="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" (or alternatively: "move", "load", "store") that move "clumps" of objects/marks from register to register in one action.
#'''A 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]]).
##'''Arithmetic''': Arithmetic instructions may operate on all registers or on a specific register, such as an accumulator. Typically, they are selected from the following sets, though exceptions exist: 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 (<math>r_1,r_2</math>), Proper-Subtract (<math>r_1,r_2</math>), Increment accumulator, Decrement accumulator, Clear accumulator, Add the contents of register <math>r</math> to the accumulator, Proper-Subtract the contents of register <math>r</math> from the accumulator }  Augmented RAM, RASP: Includes all of the reduced instructions as well as: { Multiply, Divide, various [[Boolean function|Boolean bit-wise operations]] (left-shift, bit test, etc.) }.
##'''Control''': Counter machine models: Optionally include { Copy (<math>r_1,r_2</math>) }.  RAM and RASP models: Most include { Copy (<math>r_1,r_2</math>) }, or { Load Accumulator from <math>r</math>, Store accumulator into <math>r</math>, Load Accumulator with an immediate constant }.  All models: Include at least one conditional "jump" (branch, goto) following the test of a register, such as { Jump-if-zero, Jump-if-not-zero (i.e., Jump-if-positive), Jump-if-equal, Jump-if-not-equal }.  All models optionally include: { unconditional program jump (goto) }.
##'''Register-addressing method''':
##*Counter machine: no indirect addressing, immediate operands possible in highly atomized models
##*RAM and RASP: indirect addressing available, immediate operands typical
##'''Input-output''': optional in all models
#'''State register''': A special [[Instruction register|Instruction Register]] (IR), distinct from the registers mentioned earlier, stores the current instruction to be executed along with its address in the instruction table. This register, along with its associated table, is located within the finite state machine. The IR is inaccessible in all models. In the case of RAM and RASP, for determining the "address" of a register, the model can choose either (i) the address specified by the table and temporarily stored in the IR for direct addressing, or (ii) the contents of the register specified by the instruction in the IR for indirect addressing.  It's important to note that the IR is not the "program counter" (PC) of the RASP (or conventional computer). The PC is merely another register akin to an accumulator but specifically reserved for holding the number of the RASP's current register-based instruction. Thus, a RASP possesses two "instruction/program" registers: (i) the IR (finite state machine's Instruction Register), and (ii) a PC ([[Program counter|Program Counter]]) for the program stored in the registers. Additionally, aside from the PC, a RASP may also dedicate another register to the "Program-Instruction Register" (referred to by various names such as "PIR," "IR," "PR," etc.).
#'''List of labelled instructions, usually in sequential order''': A finite list of instructions <math>I_1 \ldots I_m</math>. 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 examples 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]].''<br>The instructions are usually listed in sequential order, like [[computer program]]s, unless a jump is successful. In this case, the default sequence continues in numerical order. An exception to this is the abacus<ref name="Lambek_1961"/><ref name="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<sub>true</sub>, z<sub>false</sub> ) }.
See [[McCarthy Formalism]] for more about the ''conditional expression'' "IF r=0 THEN z<sub>true</sub> ELSE  z<sub>false</sub>"<ref name="McCarthy_1960" />