Random-access machine
In computer science, random-access 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 numbers of any size. Like the counter machine, the RA-machine contains the execution instructions in the finite-state portion of the machine.
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 calls these three together with the pointer machine, "sequential machine" models, to distinguish them from "parallel random-access machine" models.
Informal description
An RA-machine consists of the following:- an infinite number of memory locations called "registers"; each register has an address which is a natural number or zero; each register can store exactly one natural number of any size, or a zero
- the instruction table, or just "table", containing execution instructions; the exact instruction set varies depending on the author; common instructions include: increment, decrement, clear to zero, copy, conditional jump, halt; other instructions are unnecessary because they can be created by combinations of instructions from the instruction set
- one special register called the "instruction register" ; this register points to the instruction being executed in the instruction table
Introduction to the model
The concept of a random-access machine 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 registers, the most common of which is called "the accumulator".Formal definition
A random-access machine 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 directly from the instruction itself, or indirectly from the contents of the "pointer" register specified in the instruction.By definition: A register is a location with both an address and a contenta single natural number. For precision we will use the quasi-formal symbolism from Boolos-Burgess-Jeffrey to specify a register, its contents, and an operation on a register:
- 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 or a name.
- → means "copy/deposit into", or "replaces", but without destruction of the source
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. A register can address itself indirectly.
Definition: The contents of source register is used by the instruction. The source register's address can be specified either directly by the instruction, or 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 directly by the instruction, or indirectly by the pointer register specified by the instruction. The source and destination registers can be one.
Refresher: The counter-machine model
The register machine has, for a memory external to its finite-state machinean unbounded collection of discrete and uniquely labelled locations with unbounded capacity, called "registers". These registers hold only natural numbers. Per a list of sequential instructions in the finite-state machine's TABLE, a few 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 visualization and to Lambek :
- :
| Instruction | Mnemonic | Action on register "r" | Action on finite-state machine's Instruction Register, IR |
| INCrement | INC | + 1 → r | + 1 → IR |
| DECrement | DEC | - 1 → r | + 1 → IR |
| Jump if Zero | JZ | IF = 0 THEN z → IR ELSE + 1 → IR | |
| Halt | H | → IR |
Base model 2: The "successor" model :
| Instruction | Mnemonic | Action on register "r" | Action on finite-state machine's Instruction Register, IR |
| CLeaR | CLR | 0 → r | + 1 → IR |
| INCrement | INC | + 1 → r | + 1 → IR |
| Jump if Equal | JE | IF = THEN z → IR ELSE + 1 → IR | |
| Halt | H | → IR |
Base model 3: Used by Elgot-Robinson in their investigation of bounded and unbounded RASPsthe "successor" model with COPY in the place of CLEAR:
| Instruction | Mnemonic | Action on register "r" | Action on finite-state machine's Instruction Register, IR |
| COPY | COPY | → r2 | + 1 → IR |
| INCrement | INC | + 1 → r | + 1 → IR |
| Jump if Equal | JE | IF = THEN z → IR ELSE + 1 → IR | |
| Halt | H | → 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 declare a reserved register e.g. call it "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, Boolos-Burgess-Jeffrey.. However, building the primitive recursive functions is difficult because the instruction sets are so... primitive. One solution is to expand a particular set with "convenience instructions" from another set:
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 i.e.:
The "indirect" operation
Example of indirect addressing
In our daily lives the notion of an "indirect operation" is not unusual.Indirection specifies a location identified as the pirate chest in "Tom_&_Becky's_cave..." that acts as a pointer to any other location : its contents provides the "address" of the target location
"under_Thatcher's_front_porch" where the real action is occurring.
Why the need for an indirect operation: Two major problems with the counter-machine model
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:- Melzak added indirection to his "hole-and-pebble" model so that his model could modify itself with a "computed goto" and provides two examples of its use. Minsky was able to demonstrate that, with suitable Gödel number encoding, the register model did not need indirection to be Turing equivalent; but it did need at least one unbounded register. As noted below, Minsky hints at the problem for a RASP but doesn't offer a solution. Elgot and Robinson proved that their RASP model P0it has no indirection capabilitycannot compute all "recursive sequential functions" if it does not have the capability of modifying its own instructions, but it can via Gödel numbers if it does. On the other hand their RASP model P'0 equipped with an "index register" can compute all the "partial recursive sequential functions" .
- Unbounded capacities of registers versus bounded capacities of state-machine instructions: The so-called finite state part of the machine is supposed to beby the normal definition of algorithmvery finite both in the number of "states" and the instructions' sizes. So how does a state machine move an arbitrarily large constant directly into a register, e.g. MOVE ? If huge constants are necessary they must either start out in the registers themselves or be created by the state machine using a finite number of instructions e.g. multiply and add subroutines using INC and DEC.
- Unbounded numbers of registers versus bounded state-machine instructions: This is more severe than the first problem. In particular, this problem arises when we attempt to build a so-called RASP, a "universal machine" that uses its finite-state machine to interpret a "program of instructions" located in its registersi.e. we are building what is nowadays called a computer with the von Neumann architecture.
Elgot and Robinson come to a similar conclusion with respect to a RASP that is "finitely determined". Indeed it can access an unbounded number of registers but only if the RASP allows "self modification" of its program instructions, and has encoded its "data" in a Gödel number.
In the context of a more computer-like model using his RPT instruction Minsky tantalizes us with a solution to the problem but offers no firm resolution. He asserts:
He offers us a bounded RPT that together with CLR and INC 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 and INC can compute the mu recursive functions. But he does not discuss "indirection" or the RAM model per se.
From the references in Hartmanis it appears that Cook has firmed up the notion of indirect addressing. This becomes clearer in the paper of Cook and Reckhow Cook is Reckhow's Master's thesis advisor. Hartmanis' modelquite similar to Melzak's modeluses two and three-register adds and subtracts and two parameter copies; Cook and Reckhow's model reduce the number of parameters 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 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 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.