In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, random-access machine (RAM) is an
abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pre ...
in the general class of
register machine
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.
Overview
The register machine gets its name from ...
s. The RAM is very similar to the
counter machine
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 ''re ...
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 (the so-called
Harvard architecture
The Harvard architecture is a computer architecture with separate storage and signal pathways for instructions and data. It contrasts with the von Neumann architecture, where program instructions and data share the same memory and pathways.
...
).
The RAM's equivalent of the
universal Turing machine
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simu ...
with its
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Progra ...
in the registers as well as its datais called the
random-access stored-program machine or RASP. It is an example of the so-called
von Neumann architecture
The von Neumann architecture — also known as the von Neumann model or Princeton architecture — is a computer architecture based on a 1945 description by John von Neumann, and by others, in the ''First Draft of a Report on the EDVAC''. The ...
and is closest to the common notion of a
computer
A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
.
Together with the
Turing machine
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 algori ...
and
counter-machine model 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 speciesthe "counter machine"of the genus "register machine."
Within the species "co ...
s, the RAM and RASP models are used for
computational complexity analysis
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved b ...
. Van Emde Boas (1990) calls these three plus the
pointer machine
In theoretical computer science a pointer machine is an "atomistic" ''abstract computational machine'' model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model.
Depending on the type, a ...
"sequential machine" models, to distinguish them from "
parallel random-access machine
In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...
" models.
Introduction to the model
The concept of a
random-access
Random access (more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any othe ...
machine (RAM) starts with the simplest model of all, the so-called
counter machine
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 ''re ...
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
A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
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
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 ''re ...
with the addition of indirect addressing. At the discretion of instruction from its
finite state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
'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''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:
*
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:
+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
37, that is, the contents of register 3 is the number "37", then 37+1 = 38 will be put into register 3.
:: Example:
→ 5; means "The contents of source register with address "3" is put into destination register with address "5". If
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
continues to be 38, now the same as
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
3, then register 3 is the destination and the instruction will do the following:
→ 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''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
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 algori ...
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
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.
Overview
The register machine gets its name from ...
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):
* :
Base model 2: The "successor" model (named after the successor function of the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
):
*
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:
*
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)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
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
s ( cf Minsky (1967), Boolos-Burgess-Jeffrey (2002) ). (How to cast the net wider to capture the ''total'' and ''partial''
mu recursive function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
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 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:
:* CLR (r) =
equiv
:* ''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.:
*
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).
The "indirect" operation
Example of indirect addressing
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
In computer programming, indirection (also called dereferencing) is the ability to reference something using a name, reference, or container instead of the value itself. The most common form of indirection is the act of manipulating a value throug ...
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.
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
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
:
* ''Melzak (1961) 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 ("Decimal representation in the scale of d" and "Sorting by magnitude", whether these are used in his proof that the model is Turing equivalent is unclear since "the program itself is left to the reader as an exercise" (p. 292)). Minsky (1961, 1967) was able to demonstrate that, with suitable (but difficult-to-use)
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 (1967) hints at the problem for a RASP but doesn't offer a solution. Elgot and Robinson (1964) proved that their RASP model P
0it has no indirection capabilitycannot compute all "recursive sequential functions" (ones that have parameters of arbitrary length) if it does not have the capability of modifying its own instructions, but it can via Gödel numbers if it does (p. 395-397; in particular figure 2 and footnote p. 395). On the other hand their RASP model P'
0 equipped with an "index register" (indirect addressing) can compute all the "partial recursive sequential functions" (the mu recursive functions) (p. 397-398).''
:''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)''
* 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 algorithm''very'' finite both in the number of "states" (instructions) and the instructions' sizes (their capacity to hold symbols/signs). So how does a state machine move an arbitrarily large constant directly into a register, e.g. MOVE (k, r) (Move constant k to register r)? 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 (but not a quasi-infinite number of these!).
::''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
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.''
* 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" (see more at
Universal Turing machine
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simu ...
) 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
A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
with the
von Neumann architecture
The von Neumann architecture — also known as the von Neumann model or Princeton architecture — is a computer architecture based on a 1945 description by John von Neumann, and by others, in the ''First Draft of a Report on the EDVAC''. The ...
.
: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 = 2
16 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
ic, 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
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
, 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
In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the five primitive recursive operators makes it possible to define ...
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!).
Bounded indirection and the primitive recursive functions
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 function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
s )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 function
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
sby 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
In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the five primitive recursive operators makes it possible to define ...
.
:''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.
Unbounded indirection and the partial recursive functions
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 ( indirect
source, r
source, direct
destination, r
destination )
: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*
s">s+ (1-i)*r
s
:For example, suppose the contents of register 3 are "5" (i.e.
5 ) and the contents of register 4 are "2" (i.e.
2 ):
:: Example: CPY ( 1, 3, 0, 4 ) = CPY ( indirect, reg 3, direct, reg 4 )
::: 1*
+ 0*3 =
= source-register address 5
::: 0*
+ 1*4 = 4 = destination-register address 4
:: Example: CPY ( 0, 3, 0, 4 )
::: 0*
+ 1*3 = 3 = source-register address 3
::: 0*
+ 1*4 = 4 = destination-register address 4
:: Example: CPY ( 0, 3, 1, 4 )
::: 0*
+ 1*3 = 3 = source-register address 3
::: 1*
+ 0*4 =
= destination-register address 2
The indirect COPY instruction
Probably the most useful of the added instructions is COPY. Indeed, Elgot-Robinson (1964) provide their models P
0 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, r
s, d, r
d ) = COPY directly from source-register directly to destination-register
: CPY (i, r
sp, d, r
d ) = COPY to destination-register indirectly using the source address to be found in the source-pointer register r
sp.
: CPY (d, r
s, i, r
dp ) = COPY contents of source-register indirectly into register using destination address to be found in the destination-pointer register r
dp.
: CPY (i, r
sp, i, r
dp ) = COPY indirectly the contents of the source register with address to be found in source-pointer register r
sp, into the destination register with address to be found in the destination-pointer register r
dp)
In a similar manner every three-register instruction that involves two source registers r
s1 r
s2 and a destination register r
d will result in 8 varieties, for example the addition:
::
s1">s1+
s2">s2→ r
d
will yield:
* ADD ( d, r
s1, d, r
s2, d, r
d )
* ADD ( i, r
sp1, d, r
s2, d, r
d )
* ADD ( d, r
s1, i, r
sp2, d, r
d )
* ADD ( i, r
sp1, i, r
sp2, d, r
d )
* ADD ( d, r
s1, d, r
s2, i, r
dp )
* ADD ( i, r
sp1, d, r
s2, i, r
dp )
* ADD ( d, r
s1, i, r
sp2, i, r
dp )
* ADD ( i, r
sp1, i, r
sp2, i, r
dp )
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.
The notion of "accumulator A"
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:
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 ) = INCA
However, 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
Mix, mixes or mixing may refer to:
Persons & places
* Mix (surname)
** Tom Mix (1880-1940), American film star
* nickname of Mix Diskerud (born Mikkel, 1990), Norwegian-American soccer player
* Mix camp, an informal settlement in Namibia
* Mix ...
computer) uses two names called LOAD and STORE. Here we are adding the "i/d" parameter:
: LDA ( d/i, r
s ) =
def CPY ( d/i, r
s, d, A )
: STA ( d/i, r
d ) =
def CPY ( d, A, d/i, r
d )
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 =
+1 → A
: Example: ADDA (r
s) =
+
s">s→ A
: Example: MULA (r
s) =
*
s">s→ 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 :
:.
*
George Boolos
George Stephen Boolos (; 4 September 1940 – 27 May 1996) was an American philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.
Life
Boolos is of Greek-Jewish descent. He graduated with an A.B. in ...
,
John P. Burgess
John Patton Burgess (born 5 June 1948) is an American philosopher. He is John N. Woodhull Professor of Philosophy at Princeton University where he specializes in logic and philosophy of mathematics.
Education and career
Burgess received his Ph.D ...
,
Richard Jeffrey
Richard Carl Jeffrey (August 5, 1926 – November 9, 2002) was an American philosopher, logician, and probability theorist. He is best known for developing and championing the philosophy of radical probabilism and the associated heuristic of pr ...
(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 comparedthe Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
*
Arthur Burks
Arthur Walter Burks (October 13, 1915 – May 14, 2008) was an American mathematician who worked in the 1940s as a senior engineer on the project that contributed to the design of the ENIAC, the first general-purpose electronic digital computer. ...
,
Herman Goldstine
Herman Heine Goldstine (September 13, 1913 – June 16, 2004) was a mathematician and computer scientist, who worked as the director of the IAS machine at Princeton University's Institute for Advanced Study and helped to develop ENIAC, the ...
,
John von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
(1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp. 92ff in
Gordon Bell
Chester Gordon Bell (born August 19, 1934) is an American electrical engineer and manager. An early employee of Digital Equipment Corporation (DEC) 1960–1966, Bell designed several of their PDP machines and later became Vice President of Engi ...
and
Allen Newell
Allen Newell (March 19, 1927 – July 19, 1992) was a researcher in computer science and cognitive psychology at the RAND Corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department ...
(1971), ''Computer Structures: Readings and Examples'', mcGraw-Hill Book Company, New York. .
*
Stephen A. Cook and Robert A. Reckhow (1973), ''Time-bounded random access machines'', Journal of Computer Systems Science 7(4):354-375.
*
Martin Davis (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
*
Calvin Elgot Calvin may refer to:
Names
* Calvin (given name)
** Particularly Calvin Coolidge, 30th President of the United States
* Calvin (surname)
** Particularly John Calvin, theologian
Places
In the United States
* Calvin, Arkansas, a hamlet
* Calvin To ...
and
Abraham Robinson
Abraham Robinson (born Robinsohn; October 6, 1918 – April 11, 1974) was a mathematician who is most widely known for development of nonstandard analysis, a mathematically rigorous system whereby infinitesimal and infinite numbers were reincorpo ...
(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
John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is the IBM Pro ...
,
Jeffrey Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...
(1979). ''Introduction to Automata Theory, Languages and Computation'', 1st ed., Reading Mass: Addison-Wesley. . A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
*
Stephen Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
(1952), ''Introduction to Metamathematics'', North-Holland Publishing Company, Amsterdam, Netherlands. .
*
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
(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
Joachim "Jim" Lambek (5 December 1922 – 23 June 2014) was a German-born Canadian mathematician. He was Peter Redpath Emeritus Professor of Pure Mathematics at McGill University, where he earned his PhD degree in 1950 with Hans Zassenhaus as ...
(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
The ''Canadian Mathematical Bulletin'' (french: Bulletin Canadien de Mathématiques) is a mathematics journal, established in 1958 and published quarterly by the Canadian Mathematical Society. The current editors-in-chief of the journal are Antoni ...
, 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. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
*
* 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
John is a common English name and surname:
* John (given name)
* John (surname)
John may also refer to:
New Testament
Works
* Gospel of John, a title often shortened to John
* First Epistle of John, often shortened to 1 John
* Second ...
and
H. E. Sturgis (1961) received December 1961 ''Computability of Recursive Functions'', Journal of the Association of 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
Arnold Schönhage (born 1 December 1934 in Lockhausen, now Bad Salzuflen) is a German mathematician and computer scientist.
Schönhage was professor at the Rheinische Friedrich-Wilhelms-Universität, Bonn, and also in Tübingen and Konstanz. ...
(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
Peter van Emde Boas (born 3 April 1945, Amsterdam) is a Dutch computer scientist and professor at the University of Amsterdam. He gained his doctorate in 1974 under Adriaan van Wijngaarden.
The Van Emde Boas tree
A van Emde Boas tree (), also k ...
, "Machine Models and Simulations" pp. 3–66, in:
Jan van Leeuwen
Jan van Leeuwen (born December 17, 1946, in Waddinxveen) is a Dutch computer scientist and Emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University. , ed. ''Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', The MIT PRESS/Elsevier, 1990. (volume A). QA 76.H279 1990. van Emde Boas's treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980{{spaced ndashit 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.
Register machines