Editing Random-access machine (section)

==Introduction to the model==
The concept of a [[random-access]] machine (RAM) starts with the simplest model of all, the so-called [[counter machine]] model. Two additions move it away from the counter machine, however. The first enhances the machine with the convenience of indirect addressing; the second moves the model toward the more conventional accumulator-based [[computer]] with the addition of one or more auxiliary (dedicated) registers, the most common of which is called "the accumulator".

=== Formal definition ===
A ''random-access machine'' (RAM) is an abstract computational-machine model identical to a multiple-register [[counter machine]] with the addition of indirect addressing. At the discretion of instruction from its [[finite-state machine]]'s TABLE, the machine derives a "target" register's address either (i) directly from the instruction itself, or (ii) indirectly from the ''contents'' (e.g. number, label) of the "pointer" register specified in the instruction.

By definition: A ''register'' is a location with both an ''address'' (a unique, distinguishable designation/locator equivalent to a natural number) and a ''content''{{spaced ndash}}a single natural number. For precision we will use the quasi-formal symbolism from Boolos-Burgess-Jeffrey (2002) to specify a register, its contents, and an operation on a register:
* [r] means "the contents of register with address r". The label "r" here is a "variable" that can be filled with a natural number or a letter (e.g. "A") or a name.
* → means "copy/deposit into", or "replaces", but without destruction of the source
:: Example: [3] +1 → 3; means "The contents of source register with address "3", plus 1, is put into destination register with address "3" (here source and destination are the same place). If [3]=37, that is, the contents of register 3 is the number "37", then 37+1 = 38 will be put into register 3.

:: Example: [3] → 5; means "The contents of source register with address "3" is put into destination register with address "5". If [3]=38, that is, the contents of register 3 is the number 38, then this number will be put into register 5.  The contents of register 3 are not disturbed by this operation, so [3] continues to be 38, now the same as [5].

Definition: A ''direct'' instruction is one that specifies ''in the instruction itself'' the address of the source or destination register whose contents will be the subject of the instruction.
Definition: An ''indirect instruction'' is one that specifies a "pointer register", the contents of which is the address of a "target" register. The target register can be either a source or a destination (the various COPY instructions provide examples of this). A register can address itself indirectly.
:For want of a standard/convention this article will specify "direct/indirect", abbreviated as "d/i", as a parameter (or parameters) in the instruction:
::Example: COPY ( '''d''', A, '''i''', N ) means directly '''d''' get the source register's address (register "A") from the instruction itself but indirectly '''i''' get the destination address from pointer-register N. Suppose [N]=3, then register 3 is the destination and the instruction will do the following: [A] → 3.

Definition: The contents of ''source register'' is used by the instruction. The source register's address can be specified either (i) directly by the instruction, or (ii) indirectly by the pointer register specified by the instruction.

Definition: The contents of the ''pointer register'' is the ''address'' of the "target" register.

Definition: The contents of the ''pointer register'' points to the ''target register''{{spaced ndash}}the "target" may be either a source or a destination register.

Definition: The ''destination register'' is where the instruction deposits its result. The source register's address can be specified either (i) directly by the instruction, or (ii) indirectly by the pointer register specified by the instruction. The source and destination registers can be one.

=== 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
|}

===Creating "convenience instructions" from the base sets===
The three base sets 1, 2, or 3 above are equivalent in the sense that one can create the instructions of one set using the instructions of another set (an interesting exercise: a hint from Minsky (1967){{spaced ndash}}declare a reserved register e.g. call it "0" (or Z for "zero" or E for "erase") to contain the number 0). The choice of model will depend on which an author finds easiest to use in a demonstration, or a proof, etc.

Moreover, from base sets 1, 2, or 3 we can create ''any'' of the [[primitive recursive function]]s ( cf Minsky (1967), Boolos-Burgess-Jeffrey (2002) ). (How to cast the net wider to capture the ''total'' and ''partial'' [[mu recursive function]]s will be discussed in context of indirect addressing). However, building the primitive recursive functions is difficult because the instruction sets are so ... primitive (tiny). One solution is to expand a particular set with "convenience instructions" from another set:
:''These will not be subroutines in the conventional sense but rather ''blocks'' of instructions created from the base set and given a mnemonic. In a formal sense, to use these blocks we need to either (i) "expand" them into their base-instruction equivalents{{spaced ndash}}they will require the use of temporary or "auxiliary" registers so the model must take this into account, or (ii) design our machines/models with the instructions 'built in'.''
:Example: Base set 1. To create CLR (r) use the block of instructions to count down register r to zero. Observe the use of the hint mentioned above:
:* CLR (r) =<sub>equiv</sub>
:* ''loop'': JZ (r, ''exit'')
::* DEC (r)
::* JZ (0, ''loop'')
:* ''exit'': etc.

Again, all of this is for convenience only; none of this increases the model's intrinsic power.

For example: the most expanded set would include each unique instruction from the three sets, plus unconditional jump J (z) i.e.:
* { CLR (r), DEC (r), INC (r), CPY ( r<sub>s</sub>, r<sub>d</sub> ), JZ (r, z), JE ( r<sub>j</sub>, r<sub>k</sub>, z ), J(z) }

Most authors pick one or the other of the conditional jumps, e.g. Shepherdson-Sturgis (1963) use the above set minus JE (to be perfectly accurate they use JNZ{{spaced ndash}}Jump if ''Not'' Zero in place of JZ; yet another possible convenience instruction).