Random-access stored-program machine

Last updated June 26, 2023

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: Unlike 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.

5:031815JZ18,15; if [18] is zero, jump to 15 to end the program0218DEC18; Decrement [18]0119INC19; Increment [19]031505JZ15,5; If [15] is zero, jump to 5 to repeat the loop (use Halt to simulate unconditional jump)15:00H; Halt18:n; Source value to copy19:; Destination for copy

The program-instructions available in this RASP machine will be a simple set to keep the example short:

Instruction	Mnemonic	Action on register "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 )	none	IF [r] = 0 THEN z → IR ELSE [IR] +1 → IR
Halt	H	none	[IR] → IR

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 ⟪h_a⟫,⟨h_a⟩; CPY ⟨h_a⟩,⟪h_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:

	PC	IR
hole # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
program, parameters →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	H			n
encoded program →	5				3	18	15	2	18	1	19	3	15	5	0			n
state machine instructions ↓

!

Tradition divides the state-machine's actions into two major "phases" called Fetch and Execute. We will observe below that there are "sub-phases" within these two major phases. There is no agreed-to convention; every model will require its own precise description.

Fetch phase

The state machine has access to all the registers, both directly and indirectly. So it adopts #1 as "the program counter" PC. The role of the program counter will be to "keep the place" in the program's listing; the state machine has its own state register for its private use.

Upon start, the state machine expects to find a number in the PC—the first "Program-Instruction" in the program (i.e. at #5).

(Without the use of the indirect COPYs, the task of getting the pointed-to program-instruction into #2 is a bit arduous. The state machine would indirectly decrement the pointed-to register while directly incrementing (empty) register #2. During the "parse" phase it will restore the sacrificed contents of #5 by sacrificing the count in #2.)

The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:

copy indirect from i and direct to j: CPY ⟪h_i⟫,⟨h_j⟩
copy direct from i and indirect to j: CPY ⟨h_i⟩,⟪h_j⟫

The following example shows what happens during the state-machine's "fetch" phase. The state-machine's operations are listed on the column labelled "State machine instruction ↓". Observe that at the end of the fetch, register #2 contains the numerical value 3 of the "operation code" ("opcode") of the first instruction JZ:

			PC	PIR
		hole # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		program, parameters →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	H			n
		encoded program →	5				3	18	15	2	18	1	19	3	15	5	0			n
step		state machine instructions ↓

1	fetch_instr:	CPY ⟪1⟫,⟨2⟩	5 i	[3]			[3]	18	15	2	18	1	19	3	15	5	0			n

Parse phase

Now that the number of the program-instruction (e.g. 3 = "JZ") is in register #2 -- the "Program-Instruction Register" PIR—the state machine proceeds to decrement the number until the IR is empty:

If the IR were empty before decrement then the program-instruction would be 0 = HALT, and the machine would jump to its "HALT" routine. After the first decrement, if the hole were empty the instruction would be INC, and the machine would jump to instruction "inc_routine". After the second decrement, the empty IR would represent DEC, and the machine would jump to the "dec_routine". After the third decrement, the IR is indeed empty, and this causes a jump to the "JZ_routine" routine. If an unexpected number were still in the IR, then the machine would have detected an error and could HALT (for example).

			PC	IR
		hole # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		program, parameters →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	H			n
		encoded program →	5				3	18	15	2	18	1	19	3	15	5	0			n
		state machine instructions ↓

		CPY ⟪1⟫,⟨2⟩	5 i	[3]			[3]	18	15	2	18	1	19	3	15	5	0			n
		JZ 2,halt	5	3			3	18	15	2	18	1	19	3	19	5	0			n
3		DEC 2	5	2			3	18	15	2	18	1	19	3	15	5	0			n
4		JZ 2,inc_routine:	5	2			3	18	15	2	18	1	19	3	15	5	0			n
5		DEC 2	5	1			3	18	15	2	18	1	19	3	15	5	0			n
6		JZ 2,dec_routine	5	1			3	18	15	2	18	1	19	3	15	5	0			n
7		DEC 2	5	0			3	18	15	2	18	1	19	3	15	5	0			n
8		JZ 2, JZ_routine	5	0 !
—	halt:	HALT	5	3			3	18	15	2	18	1	19	3	15	5	0			n
—	inc_routine:	etc.	5	3			3	18	15	2	18	1	19	3	15	5	0			n
—	dec_routine:	etc.	5	3			3	18	15	2	18	1	19	3	15	5	0			n
9	JZ_routine:	etc.	5	3			3	18	15	2	18	1	19	3	15	5	0			n

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).

			PC	IR
		hole # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		program, parameters →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	H			n
		encoded program →	5				3	18	15	2	18	1	19	3	15	5	0			n
step		state machine instructions ↓

9	JZ_routine	INC 1	[6]	3			3	18	15	2	18	1	19	3	15	5	0			n
10		CPY ⟪1⟫,⟨2⟩	6 i	[18]			3	[18]	15	2	18	1	19	3	15	5	0			n
11	test hole:	CPY ⟪2⟫,⟨3⟩	6	18 i	[n]		3	18	15	2	18	1	19	3	15	5	0			[n]
12	test hole:	JZ 3, jump	6	18 i	[n]		3	18	15	2	18	1	19	3	15	5	0			n
					n															n
13	no_jump:	INC 1	[7]	18	n		3	18	15	2	18	1	19	3	15	5	0			n
14		INC 1	[8]	18	n		3	18	15	2	18	1	19	3	15	5	0			n
15		J fetch_instr	8	18	n		3	18	15	2	18	1	19	3	15	5	0			n
1	fetch_instr:	CPY ⟪1⟫,⟨2⟩	8 i	[2]	n		3	18	15	[2]	18	1	19	3	15	5	0			n
2	parse:	etc.

13	jump:	INC 1	[7]	18	n		3	18	15	2	18	1	19	3	15	5	0			n
14		CPY ⟪1⟫,⟨1⟩	[15]	18	n		3	18	[15]	2	18	1	19	3	15	5	0			n
15		J fetch_instr	15	18	n		3	18	15	2	18	1	19	3	15	5	0			n
1	fetch_instr:	CPY ⟪1⟫,⟨2⟩	15 i	[0]	n		3	18	15	2	18	1	19	3	15	5	[0]			n
2	parse:	etc.

Execute phase INC, DEC

The following completes the RAM's state-machine interpretation of program-instructions, INC h, DEC h and thus completes the demonstration of how a RAM can "impersonate" a RASP:

Target program instruction set: { INC h; DEC h; JZ h,xxx, HALT }

Without indirect state-machine instructions INCi and DECi, to execute the INC and DEC program-instructions the state machine must use indirect copy to get the contents of the pointed-to register into spare register #3, DEC or INC it, and then use indirect copy to send it back to the pointed-to register.

			PC	IR
		hole # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		program, parameters →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	H			n
		encoded program →	5				3	18	15	2	18	1	19	3	15	5	0			n
		state machine instructions ↓

15		J fetch_instr	8	18	n		3	18	15	2	18	1	19	3	15	5	0			n
16	fetch_instr:	CPY ⟪1⟫,⟨2⟩	8 i	[2]	n		3	18	15	2	18	1	19	3	15	5	0			n
17	parse:	JZ 2,halt	8	2	n		3	18	15	2	18	1	19	3	15	5	0			n
18		DEC 2	8	[1]	n		3	18	15	2	18	1	19	3	15	5	0			n
19		JZ 2, inc_routine:	8	1	n		3	18	15	2	18	1	19	3	15	5	0			n
20		DEC 2	8	[0]	n		3	18	15	2	18	1	19	3	15	5	0			n
21		JZ 2, dec_routine:	8	0 !	n		3	18	15	2	18	1	19	3	15	5	0			n
22	dec_routine:	INC 1	9	0	n		3	18	15	2	18	1	19	3	15	5	0			n
23		CPY ⟪1⟫,⟨2⟩	9 i	18	n		3	18	15	2	18	1	19	3	15	5	0			n
24		CPY ⟪2⟫,⟨3⟩	9	18 i	n		3	18	15	2	18	1	19	3	15	5	0			n
25		JZ 3,*+2	9	18	n		3	18	15	2	18	1	19	3	15	5	0			n
26		DEC 3	9	18	n-1		3	18	15	2	18	1	19	3	15	5	0			n
27		CPY ⟨3⟩,⟪2⟫	9	18 i	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
28		INC 1	10	18	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
29		J fetch_instr	10	18	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1

30	fetch_instr:	CPY ⟪1⟫,⟨2⟩	10 i	1	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
31	parse:	JZ 2,halt	10	1	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
32		DEC 2	10	0	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
33		JZ 2,inc_routine:	10	0 !	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
34	inc_routine:	INC 1	11	0	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
35		CPY ⟪1⟫,⟨2⟩	11 i	19	n-1		3	18	15	2	18	1	19	3	15	5	0			n-1
36		CPY ⟪2⟫,⟨3⟩	11	19 i	0		3	18	15	2	18	1	19	3	15	5	0			n-1	0
37		INC 3	11	19	1		3	18	15	2	18	1	19	3	15	5	0			n-1	0
38		CPY ⟨3⟩,⟪2⟫	11	19 i	1		3	18	15	2	18	1	19	3	15	5	0			n-1	1
39		INC 1	12	19	1		3	18	15	2	18	1	19	3	15	5	0			n-1	0
40		J fetch_instr	12	19	1		3	18	15	2	18	1	19	3	15	5	0			n-1	0
41	fetch_instr:	etc.	12	19	1		3	18	15	2	18	1	19	3	15	5	0			n-1	0

Alternate instructions: Although the demonstration resulted in a primitive RASP of only four instructions, the reader might imagine how an additional instruction such as "ADD ⟨h⟩" or "MULT ⟨h_a⟩,⟪h_b>might be done.

Self-Modifying RASP programs

When a RAM is acting as a RASP, something new has been gained: unlike the RAM, the RASP has the capacity for self-modification of its program-instructions (the state-machine instructions are frozen, unmodifiable by the machine). Cook-Reckhow (1971) (p. 75) comment on this in their description of their RASP model, as does Hartmanis (1971) (pp. 239ff)

An early description of this notion can be found in Goldstine-von Neumann (1946):

"We need an order [instruction] that can substitute a number into a given order... By means of such an order the results of a computation can be introduced into the instructions governing that or a different computation" (p. 93)

Such an ability makes the following possible:

subroutines -- the calling routine (or perhaps the subroutine) stores the return address "return_address" in the subroutine's last command, i.e. "JMP return_address"
so-called JUMP-tables
self-modifying code

RASP program-instruction set of Cook and Reckhow (1973)

In an influential paper Stephen A. Cook and Robert A. Reckhow define their version of a RASP:

"The Random Access Stored-Program Machine (RASP) described here is similar to the RASP's described by Hartmanis [1971]" (p. 74).

Their purpose was to compare execution-times of the various models: RAM, RASP and multi-tape Turing machine for use in the theory of complexity analysis.

The salient feature of their RASP model is no provision for indirect program-instructions (cf their discussion p. 75). This they achieve by requiring the program to modify itself: if necessary an instruction can modify the "parameter" (their word, i.e. "operand") of a particular instruction. They have designed their model so each "instruction" uses two consecutive registers, one for the "operation code" (their word) and the parameter "either an address or an integer constant".

Their RASP's registers are unbounded in capacity and unbounded in number; likewise their accumulator AC and instruction counter IC are unbounded. The instruction set is the following:

operation	mnemonic	operation code	description
load constant	LOD, k	1	put constant k into accumulator
add	ADD, j	2	add contents of register j to accumulator
subtract	SUB, j	3	subtract contents of register j from accumulator
store	STO, j	4	copy contents of accumulator into register j
branch on positive accumulator	BPA, xxx	5	IF contents of accumulator > 0 THEN jump to xxx ELSE next instruction
read	RD, j	6	next input into register j
print	PRI, j	7	output contents of register j
halt	HLT	any other - or + integer	stop

Related Research Articles

The Data General Nova is a series of 16-bit minicomputers released by the American company Data General. The Nova family was very popular in the 1970s and ultimately sold tens of thousands of units.

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.

In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation.

The Intel MCS-51 is a single chip microcontroller (MCU) series developed by Intel in 1980 for use in embedded systems. The architect of the Intel MCS-51 instruction set was John H. Wharton. Intel's original versions were popular in the 1980s and early 1990s, and enhanced binary compatible derivatives remain popular today. It is a complex instruction set computer, but also has some of the features of RISC architectures, such as a large register set and register windows, and has separate memory spaces for program instructions and data.

A one-instruction set computer (OISC), sometimes referred to as an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode. With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions. OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research. The first carbon nanotube computer is a 1-bit one-instruction set computer.

An index register in a computer's CPU is a processor register used for pointing to operand addresses during the run of a program. It is useful for stepping through strings and arrays. It can also be used for holding loop iterations and counters. In some architectures it is used for read/writing blocks of memory. Depending on the architecture it maybe a dedicated index register or a general-purpose register. Some instruction sets allow more than one index register to be used; in that case additional instruction fields may specify which index registers to use.

In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent.

In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a virtual machine in which the primary interaction is moving short-lived temporary values to and from a push down stack. In the case of a hardware processor, a hardware stack is used. The use of a stack significantly reduces the required number of processor registers. Stack machines extend push-down automata with additional load/store operations or multiple stacks and hence are Turing-complete.

In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the counter machine, The RAM has its instructions in the finite-state portion of the machine.

Addressing modes are an aspect of the instruction set architecture in most central processing unit (CPU) designs. The various addressing modes that are defined in a given instruction set architecture define how the machine language instructions in that architecture identify the operand(s) of each instruction. An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.

The National Semiconductor COP8 is an 8-bit CISC core microcontroller. COP8 is an enhancement to the earlier COP400 4-bit microcontroller family. COP8 main features are:

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.

A Post–Turing machine is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974. Later in 1980, Davis used the name "Turing–Post program".

In theoretical computer science, a pointer machine is an atomistic abstract computational machine model akin to the random-access machine. A pointer algorithm could also be an algorithm restricted to the pointer machine model.

A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm.

A counter machine is an abstract machine used in a formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer, and a list of arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorithms may be designed in such a matter to avoid interlocking, the simultaneous writing operation by two threads to the same memory address.

Although some authors use the name "register machine" synonymously with "counter machine", this article will give details and examples of only of the most primitive species – the "counter machine" – of the genus "register machine."

The PDP-11 architecture is a CISC instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). It is implemented by central processing units (CPUs) and microprocessors used in PDP-11 minicomputers. It was in wide use during the 1970s, but was eventually overshadowed by the more powerful VAX architecture in the 1980s.

The PIC instruction set refers to the set of instructions that Microchip Technology PIC or dsPIC microcontroller supports. The instructions are usually programmed into the Flash memory of the processor, and automatically executed by the microcontroller on startup.

The STM8 is an 8-bit microcontroller family by STMicroelectronics. The STM8 microcontrollers use an extended variant of the ST7 microcontroller architecture. STM8 microcontrollers are particularly low cost for a full-featured 8-bit microcontroller.

References

Often both the RAM and RASP machines are presented together in the same article. These have been copied over from Random-access machine; with a few exceptions, these references are the same as those at Register machine.

George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and two recursion models.
Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssotsky of the Bell telephone Laboratories and with Dr. H. Wang of Oxford University
Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. ISBN 0-13-165449-7. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association for Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

Arnold Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36–37
Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing in: Jan van Leeuwen, ed. "Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.

van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.

Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.