Random access stored program machine

In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

The RASP is a Random Access Machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded (infinite in capacity); whether the number of registers is finite is model-specific. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine. The RASP is an example of the von Neumann architecture whereas the RAM is an example of the Harvard architecture.

The RASP is closest of all the abstract models to the common notion of computer. But unlike actual computers the RASP model usually has a very simple instruction set, greatly reduced from those of CISC and even RISC processors to the simplest arithmetic, register-to-register "moves", and "test/jump" instructions. Some models have a few extra registers such as an accumulator.

Together with the Register machine, the RAM, and the pointer machine the RASP makes up the four common sequential machine models, called this to distinguish them from the "parallel" models (e.g. parallel random access machine) [cf. van Emde Boas (1990)] .

Informal definition: Random Access Stored Program model (RASP)

Nutshell description of a RASP::The RASP is a Universal Turing Machine (UTM) built on a Random access machine RAM chassis.

The reader will remember that the UTM is a Turing machine with a "Universal" finite-state table of instructions that can interpret any well-formed "program" written on the tape as a string of Turing 5-tuples, hence its universality. While the classical UTM model expects to find Turing 5-tuples on its tape, any program-set imaginable can be put there given that the Turing machine expects to find them -- given that its finite-state table can interpret them and convert them to the desired action. Along with the program, printed on the tape will be the input data/parameters/numbers (usually to the program's right), and eventually the output data/numbers (usually to the right of both, or intermingled with the input, or replacing it). The "user" must position the Turing machine's head over the first instruction, and the input must be placed in a specified place and format appropriate to both the program-on-tape and the finite-state machine's instruction-table.

The RASP mimics this construction: it places the "program" and "data" in the holes (registers). But unlike the UTM the RASP proceeds to "fetch" its instructions in a sequential manner, unless the conditional test sends it elsewhere.

A point of confusion: two sets of instructions: Like the UTM, the RASP model has two sets of instructions -- the state machine table of instructions (the "interpreter") and the "program" in the holes. The two sets do not have to be drawn from the same set.

An example of a RAM working as a RASP

The following example of a program will move the contents of register (hole) #18 to register (hole) #19, erasing contents of #18 in the process. The "program"-instructions will be a simple set to keep the example short::Target RASP program-instructions:::{ INC h; DEC h; JZ h,xxx }

To ease the example we will equip the "state machine" of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions::RAM state machine instructions:::{ INC h; DEC h; JZ h,xxx; CPY <a>>,a>; CPY a>,<a>> }

As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" -- converts to action -- the program:

Execute phase, JZ_routine

Now the state machine knows what program-instruction to execute; indeed it has jumped to the "JZ_routine" sequence of instructions. The JZ instruction has 2 operands -- (i) the number of the register to test, and (ii) the address to go to if the test is successful (the hole is empty).

(i) Operand fetch -- which register to test for empty?: Analogous to the fetch phase, the finite state machine moves the contents of the register pointed to by the PC, i.e. hole #6, into the Program-Instruction Register PIR #2. It then uses the contents of register #2 to point to the register to be tested for zero, i.e. register #18. Hole #18 contains a number "n". To do the test, now the state machine uses the contents of the PIR to indirectly copy the contents of register #18 into a spare register, #3. So there are two eventualities (ia), register #18 is empty, (ib) register #18 is not empty. (ia): If register #3 is empty then the state machine jumps to (ii) Second operand fetch -- fetch the jump-to address.

(ib): If register #3 is not empty then the state machine can skip (ii) Second operand fetch. It simply increments twice the PC and then unconditionally jumps back to the instruction-fetch phase, where it fetches program-instruction #8 (DEC).

(ii) Operand fetch -- jump-to address. If register #3 is empty, the state machine proceeds to use the PC to indirectly copy the contents of the register it points to (#8) into "itself". Now the PC holds the jump-to address 15. Then the state machine unconditionally goes back to the instruction fetch phase, where it fetches program-instruction #15 (HALT).

References

Often both the RAM and RASP machines are presented together in the same article. See Register machine and Random access machine for references;