Editing Random-access machine (section)

=== Refresher: The counter-machine model ===
:''Melzak (1961) provides an easy visualization of a counter machine: its "registers" are holes in the ground, and these holes hold pebbles. Per an instruction, into and out of these holes "the computer" (person or machine) adds (INCrements) or removes (DECrements) a single pebble. As needed, additional pebbles come from, and excess pebbles go back into, an infinite supply; if the hole is too small to accommodate the pebbles the "computer" digs the hole bigger.''

:''Minsky (1961) and Hopcroft-Ullman 1979 (p. 171) offer the visualization of a multi-tape [[Turing machine]] with as many left-ended tapes as "registers". Each tape's length is unbounded to the right, and every square is blank except for the left end, which is marked. The ''distance'' of a tape's "head" from its left end, measured in numbers of tape-squares, represents the natural number in "the register". To DECrement the count of squares the tape head moves left; INCrement it moves right. There is no need to print or erase marks on the tape; the only conditional instructions are to check to see if the head is at the left end, by testing a left-end mark with a "Jump-if-marked instruction".''

:''The following instruction "mnemonics" e.g. "CLR (r)" are arbitrary; no standard exists.''

The [[register machine]] has, for a memory external to its finite-state machine{{spaced ndash}}an unbounded (cf: footnote|countable and unbounded) collection of discrete and uniquely labelled locations with ''unbounded'' capacity, called "registers". These registers hold only natural numbers (zero and positive integers). Per a list of sequential instructions in the finite-state machine's TABLE, a few (e.g. 2) types of primitive operations operate on the contents of these "registers". Finally, a ''conditional-expression'' in the form of an ''IF-THEN-ELSE'' is available to test the contents of one or two registers and "branch/jump" the finite-state machine out of the default instruction-sequence.

'''Base model 1''': The model closest to Minsky's (1961) visualization and to Lambek (1961):
* { INCrement contents of register r, DECrement contents of register r, ''IF'' contents of register r is Zero ''THEN'' Jump to instruction I<sub>z</sub> ''ELSE'' continue to next instruction }:

{|class="wikitable"
|-  style="text-align:center; font-size:9pt; font-weight:bold; vertical-align:bottom;"
!  style="width:63.6; height:12px;"| Instruction
! style="width:67.8;"| Mnemonic
! style="width:130.2;"| Action on register(s) "r"
! style="width:240.6;"| Action on finite-state machine's Instruction Register, IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| INCrement
|| INC ( r )
|  style="text-align:center; "| [r] + 1 → r
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| DECrement
|| DEC ( r )
|  style="text-align:center; "| [r] - 1 → r
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Jump if Zero
|| JZ ( r, z )
| {{CNone|none}}
|  style="text-align:center; "| IF [r] = 0 THEN z → IR  ELSE [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Halt
|| H
| {{CNone|none}}
|  style="text-align:center; "| [IR]  → IR
|}

'''Base model 2''': The "successor" model (named after the successor function of the [[Peano axioms]]):
* { INCrement the contents of register r, CLeaR the contents of register r, ''IF'' contents of register r<sub>j</sub> Equals the contents of register r<sub>k</sub> ''THEN'' Jump to instruction I<sub>z</sub> ''ELSE'' goto to next instruction }

{|class="wikitable"
|-  style="text-align:center; font-size:9pt; font-weight:bold; vertical-align:bottom;"
! style="width:63.6; height:12px;"| Instruction
! style="width:67.8;"| Mnemonic
! style="width:130.2;"| Action on register(s) "r"
! style="width:240.6;"| Action on finite-state machine's Instruction Register, IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| CLeaR
|| CLR ( r )
|  style="text-align:center; "| 0 → r
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| INCrement
|| INC ( r )
|  style="text-align:center; "| [r] + 1 → r
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Jump if Equal
|| JE (r1, r2, z)
| {{CNone|none}}
|  style="text-align:center; "| IF [r1] = [r2] THEN z → IR  ELSE [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Halt
|| H
| {{CNone|none}}
|  style="text-align:center; "| [IR]  → IR
|}

'''Base model 3''': Used by Elgot-Robinson (1964) in their investigation of bounded and unbounded RASPs{{spaced ndash}}the "successor" model with COPY in the place of CLEAR:
* { INCrement the contents of register r, COPY the contents of register r<sub>j</sub> to register r<sub>k</sub>, ''IF'' contents of register r<sub>j</sub> Equals the contents of register r<sub>k</sub> ''then'' Jump to instruction I<sub>z</sub> ''ELSE'' goto to next instruction }

{|class="wikitable"
|-  style="text-align:center; font-size:9pt; font-weight:bold; vertical-align:bottom;"
!  style="width:63.6; height:12px;"| Instruction
! style="width:67.8;"| Mnemonic
! style="width:130.2;"| Action on register(s) "r"
! style="width:240.6;"| Action on finite-state machine's Instruction Register, IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| COPY
|| COPY (r1, r2)
|  style="text-align:center; "| [r1] → r2
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| INCrement
|| INC ( r )
|  style="text-align:center; "| [r] + 1 → r
|  style="text-align:center; "| [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Jump if Equal
|| JE (r1, r2, z)
| {{CNone|none}}
|  style="text-align:center; "| IF [r1] = [r2] THEN z → IR  ELSE [IR] + 1 → IR
|-  style="font-size:9pt; vertical-align:bottom;"
|  style="height:11.4; "| Halt
|| H
| {{CNone|none}}
|  style="text-align:center; "| [IR]  → IR
|}