In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. The 'registers' are intuitively equivalent to main memory of a common computer, except for the additional ability of registers to store natural numers of any size. Like the counter machine, the RA-machine contains the execution instructions in the finite-state portion of the machine (the so-called Harvard architecture).
The RA-machine's equivalent of the universal Turing machinewith its program in the registers as well as its datais called the random-access stored-program machine or RASP-machine. It is an example of the so-called von Neumann architecture and is closest to the common notion of a computer.
Together with the Turing machine and counter-machine models, the RA-machine and RASP-machine models are used for computational complexity analysis. Van Emde Boas (1990) calls these three together with the pointer machine, "sequential machine" models, to distinguish them from "parallel random-access machine" models.
An RA-machine consists of the following:
For a description of a similar concept, but humorous, see the esoteric programming language Brainfuck.[1]
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".
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 contenta 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:
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 registerthe "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.
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 machinean 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):
| Instruction | Mnemonic | Action on register(s) "r" | Action on finite state machine's Instruction Register, IR | |
|---|---|---|---|---|
| INCrement | INC (r) | [r] + 1 → r | [IR] + 1 → IR | |
| DECrement | DEC (r) | [r] - 1 → r | [IR] + 1 → IR | |
| Jump if Zero | JZ (r, z) | IF [r] = 0 THEN z → IR ELSE [IR] + 1 → IR | ||
| Halt | H | [IR] → IR |
Base model 2: The "successor" model (named after the successor function of the Peano axioms):
| Instruction | Mnemonic | Action on register(s) "r" | Action on finite state machine's Instruction Register, IR | |
|---|---|---|---|---|
| CLeaR | CLR (r) | 0 → r | [IR] + 1 → IR | |
| INCrement | INC (r) | [r] + 1 → r | [IR] + 1 → IR | |
| Jump if Equal | JE (r1, r2, z) | IF [r1] = [r2] THEN z → IR ELSE [IR] + 1 → IR | ||
| Halt | H | [IR] → IR |
Base model 3: Used by Elgot-Robinson (1964) in their investigation of bounded and unbounded RASPsthe "successor" model with COPY in the place of CLEAR:
| Instruction | Mnemonic | Action on register(s) "r" | Action on finite state machine's Instruction Register, IR | |
|---|---|---|---|---|
| COPY | COPY (r1, r2) | [r1] → r2 | [IR] + 1 → IR | |
| INCrement | INC (r) | [r] + 1 → r | [IR] + 1 → IR | |
| Jump if Equal | JE (r1, r2, z) | IF [r1] = [r2] THEN z → IR ELSE [IR] + 1 → IR | ||
| Halt | H | [IR] → IR |
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)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 functions (cf Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (How to cast the net wider to capture the total and partial mu recursive functions 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 equivalentsthey 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:
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.:
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 JNZJump if Not Zero in place of JZ; yet another possible convenience instruction).
In our daily lives the notion of an "indirect operation" is not unusual.
Example: A treasure hunt.
At location "Tom_&_Becky's_cave_in_pirate_chest" will be where we can find a map directing us to "the treasure":
(1) We go to location "Tom_&_Becky's_cave..." and dig around until we find a wooden box
(2) Inside the box is a map to the location of the treasure: "under_Thatcher's_front_porch"
(3) We go to location "under_Thatcher's_front_porch", jackhammer away the concrete, and discover "the treasure": a sack of rusty door-knobs.
Indirection specifies a location identified as the pirate chest in "Tom_&_Becky's_cave..." that acts as a pointer to any other location (including itself): its contents (the treasure map) provides the "address" of the target location"under_Thatcher's_front_porch" where the real action is occurring.
In the following one must remember that these models are abstract models with two fundamental differences from anything physically real: unbounded numbers of registers each with unbounded capacities. The problem appears most dramatically when one tries to use a counter-machine model to build a RASP that is Turing equivalent and thus compute any partial mu recursive function:
Cook and Reckhow (1973) say it most succinctly:
The indirect instructions are necessary in order for a fixed program to access an unbounded number of registers as the inputs vary." (p. 73)
Sometimes the constant k will be created by use of CLR (r) followed by INC (r) repeated k timese.g. to put the constant k=3 into register r, i.e. 3 → r, so at the end of the instruction [r]=3: CLR (r), INC (r), INC (r), INC (r). This trick is mentioned by Kleene (1952) p. 223. The problem arises when the number to be created exhausts the number of instructions available to the finite state machine; there is always a bigger constant than the number of instructions available to the finite state machine.
Observe that the counter machine's finite state machine must call out a register explicitly (directly) by its name/number: INC (65,356) calls out register number "65,365" explicitly. If the number of registers exceeds the capability of the finite state machine to address them, then registers outside the bounds will be unreachable. For example, if the finite state machine can only reach 65,536 = 216 registers then how can it reach the 65,537th?
So how do we address a register beyond the bounds of the finite state machine? One approach would be to modify the program-instructions (the ones stored in the registers) so that they contain more than one command. But this too can be exhausted unless an instruction is of (potentially) unbounded size. So why not use just one "über-instruction"one really really big numberthat contains all the program instructions encoded into it! This is how Minsky solves the problem, but the Gödel numbering he uses represents a great inconvenience to the model, and the result is nothing at all like our intuitive notion of a "stored program computer".
Elgot and Robinson (1964) come to a similar conclusion with respect to a RASP that is "finitely determined". Indeed it can access an unbounded number of registers (e.g. to fetch instructions from them) but only if the RASP allows "self modification" of its program instructions, and has encoded its "data" in a Gödel number (Fig. 2 p. 396).
In the context of a more computer-like model using his RPT (repeat) instruction Minsky (1967) tantalizes us with a solution to the problem (cf p. 214, p. 259) but offers no firm resolution. He asserts:
"In general a RPT operation could not be an instruction in the finite-state part of the machine ... this might exhaust any particular amount of storage allowed in the finite part of the computer [sic, his name for his RAM models]. RPT operations require infinite registers of their own." (p. 214).
He offers us a bounded RPT that together with CLR (r) and INC (r) can compute any primitive recursive function, and he offers the unbounded RPT quoted above that as playing the role of μ operator; it together with CLR (r) and INC (r) can compute the mu recursive functions. But he does not discuss "indirection" or the RAM model per se.
From the references in Hartmanis (1971) it appears that Cook (in his lecture notes while at UC Berkeley, 1970) has firmed up the notion of indirect addressing. This becomes clearer in the paper of Cook and Reckhow (1973)Cook is Reckhow's Master's thesis advisor. Hartmanis' modelquite similar to Melzak's (1961) modeluses two and three-register adds and subtracts and two parameter copies; Cook and Reckhow's model reduce the number of parameters (registers called out in the program instructions) to one call-out by use of an accumulator "AC".
The solution in a nutshell: Design our machine/model with unbounded indirectionprovide an unbounded "address" register that can potentially name (call out) any register no matter how many there are. For this to work, in general, the unbounded register requires an ability to be cleared and then incremented (and, possibly, decremented) by a potentially infinite loop. In this sense the solution represents the unbounded μ operator that can, if necessary, hunt ad infinitum along the unbounded string of registers until it finds what it is looking for. The pointer register is exactly like any other register with one exception: under the circumstances called "indirect addressing" it provides its contents, rather than the address-operand in the state machine's TABLE, to be the address of the target register (including possibly itself!).
If we eschew the Minsky approach of one monster number in one register, and specify that our machine model will be "like a computer" we have to confront this problem of indirection if we are to compute the recursive functions (also called the μ-recursive functions)both total and partial varieties.
Our simpler counter-machine model can do a "bounded" form of indirectionand thereby compute the sub-class of primitive recursive functionsby using a primitive recursive "operator" called "definition by cases" (defined in Kleene (1952) p. 229 and Boolos-Burgess-Jeffrey p. 74). Such a "bounded indirection" is a laborious, tedious affair. "Definition by cases" requires the machine to determine/distinguish the contents of the pointer register by attempting, time after time until success, to match this contents against a number/name that the case operator explicitly declares. Thus the definition by cases starts from e.g. the lower bound address and continues ad nauseam toward the upper bound address attempting to make a match:
Is the number in register N equal to 0? If not then is it equal to 1? 2? 3? ... 65364? If not then we're at the last number 65365 and this had better be the one, else we have a problem!
"Bounded" indirection will not allow us to compute the partial recursive functionsfor those we need unbounded indirection aka the μ operator.
Suppose we had been able to continue on to number 65367, and in fact that register had what we were looking for. Then we could have completed our calculation successfully! But suppose 65367 didn't have what we needed. How far should we continue to go?
To be Turing equivalent the counter machine needs to either use the unfortunate single-register Minsky Gödel number method, or be augmented with an ability to explore the ends of its register string, ad infinitum if necessary. (A failure to find something "out there" defines what it means for an algorithm to fail to terminate; cf Kleene (1952) pp. 316ff Chapter XII Partial Recursive Functions, in particular p. 323-325.) See more on this in the example below.
For unbounded indirection we require a "hardware" change in our machine model. Once we make this change the model is no longer a counter machine, but rather a random-access machine.
Now when e.g. INC is specified, the finite state machine's instruction will have to specify where the address of the register of interest will come from. This where can be either (i) the state machine's instruction that provides an explicit label, or (ii) the pointer-register whose contents is the address of interest. Whenever an instruction specifies a register address it now will also need to specify an additional parameter "i/d""indirect/direct". In a sense this new "i/d" parameter is a "switch" that flips one way to get the direct address as specified in the instruction or the other way to get the indirect address from the pointer register (which pointer registerin some models every register can be a pointer registeris specified by the instruction). This "mutually exclusive but exhaustive choice" is yet another example of "definition by cases", and the arithmetic equivalent shown in the example below is derived from the definition in Kleene (1952) p. 229.
Example: CPY (indirectsource, rsource, directdestination, rdestination)
Assign a code to specify direct addressing as d="0" and indirect addressing as i="1". Then our machine can determine the source address as follows:
i*[r<sub>s</sub>] + (1-i)*rs
For example, suppose the contents of register 3 are "5" (i.e. [3]=5) and the contents of register 4 are "2" (i.e. [4]=2):
Example: CPY (1, 3, 0, 4) = CPY (indirect, reg 3, direct, reg 4)
1*[3] + 0*3 = [3] = source-register address 5
0*[4] + 1*4 = 4 = destination-register address 4
Example: CPY (0, 3, 0, 4)
0*[3] + 1*3 = 3 = source-register address 3
0*[4] + 1*4 = 4 = destination-register address 4
Example: CPY (0, 3, 1, 4)
0*[3] + 1*3 = 3 = source-register address 3
1*[4] + 0*4 = [4] = destination-register address 2
Probably the most useful of the added instructions is COPY. Indeed, Elgot-Robinson (1964) provide their models P0 and P'0 with the COPY instructions, and Cook-Reckhow (1973) provide their accumulator-based model with only two indirect instructionsCOPY to accumulator indirectly, COPY from accumulator indirectly.
A plethora of instructions: Because any instruction acting on a single register can be augmented with its indirect "dual" (including conditional and unconditional jumps, cf the Elgot-Robinson model), the inclusion of indirect instructions will double the number of single parameter/register instructions (e.g. INC (d, r), INC (i, r)). Worse, every two parameter/register instruction will have 4 possible varieties, e.g.:
CPY (d, rs, d, rd) = COPY directly from source-register directly to destination-register
CPY (i, rsp, d, rd) = COPY to destination-register indirectly using the source address to be found in the source-pointer register rsp.
CPY (d, rs, i, rdp) = COPY contents of source-register indirectly into register using destination address to be found in the destination-pointer register rdp.
CPY (i, rsp, i, rdp) = COPY indirectly the contents of the source register with address to be found in source-pointer register rsp, into the destination register with address to be found in the destination-pointer register rdp)
In a similar manner every three-register instruction that involves two source registers rs1 rs2 and a destination register rd will result in 8 varieties, for example the addition:
[r<sub>s1</sub>] + [r<sub>s2</sub>] → rd
will yield:
If we designate one register to be the "accumulator" (see below) and place strong restrictions on the various instructions allowed then we can greatly reduce the plethora of direct and indirect operations. However, one must be sure that the resulting reduced instruction-set is sufficient, and we must be aware that the reduction will come at the expense of more instructions per "significant" operation.
Historical convention dedicates a register to the accumulator, an "arithmetic organ" that literally accumulates its number during a sequence of arithmetic operations:
"The first part of our arithmetic organ ... should be a parallel storage organ which can receive a number and add it to the one already in it, which is also able to clear its contents and which can store what it contains. We will call such an organ an Accumulator. It is quite conventional in principle in past and present computing machines of the most varied types, e.g. desk multipliers, standard IBM counters, more modern relay machines, the ENIAC" (boldface in original: Goldstine and von Neumann, 1946; p. 98 in Bell and Newell 1971).
However, the accumulator comes at the expense of more instructions per arithmetic "operation", in particular with respect to what are called 'read-modify-write' instructions such as "Increment indirectly the contents of the register pointed to by register r2 ". "A" designates the "accumulator" register A:
| Label | Instruction | A | r2 | r378,426 | Description | ||
|---|---|---|---|---|---|---|---|
| . . . | 378,426 | 17 | |||||
| INCi (r2): | CPY (i, r2, d, A) | 17 | 378,426 | 17 | Contents of r2 points to r378,426 with contents "17": copy this to A | ||
| INC (A) | 18 | 378,426 | 17 | Incement contents of A | |||
| CPY (d, A, i, r2) | 18 | 378,426 | 18 | Contents of r2 points to r378,426: copy contents of A into r378,426 |
If we stick with a specific name for the accumulator, e.g. "A", we can imply the accumulator in the instructions, for example,
INC (A) = INCAHowever, when we write the CPY instructions without the accumulator called out the instructions are ambiguous or they must have empty parameters:
CPY (d, r2, d, A) = CPY (d, r2,,)
CPY (d, A, d, r2) = CPY (d, r2)
Historically what has happened is these two CPY instructions have received distinctive names; however, no convention exists. Tradition (e.g. Knuth's (1973) imaginary MIX computer) uses two names called LOAD and STORE. Here we are adding the "i/d" parameter:
LDA (d/i, rs) =def CPY (d/i, rs, d, A)
STA (d/i, rd) =def CPY (d, A, d/i, rd)
The typical accumulator-based model will have all its two-variable arithmetic and constant operations (e.g. ADD (A, r), SUB (A, r)) use (i) the accumulator's contents, together with (ii) a specified register's contents. The one-variable operations (e.g. INC (A), DEC (A) and CLR (A)) require only the accumulator. Both instruction-types deposit the result (e.g. sum, difference, product, quotient or remainder) in the accumulator.
Example: INCA = [A] +1 → A
Example: ADDA (rs) = [A] + [r<sub>s</sub>] → A
Example: MULA (rs) = [A] * [r<sub>s</sub>] → A
If we so choose, we can abbreviate the mnemonics because at least one source-register and the destination register is always the accumulator A. Thus we have :