Random-access machine

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 numbers 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 machine with its program in the registers as well as its data is 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.

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 numbers 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 machine with its program in the registers as well as its data is 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. ==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" (IR); this register points to the instruction being executed in the instruction table For a description of a similar concept, but humorous, see the esoteric programming language Brainfuck. ==Introduction to the model== 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". 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 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. ===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 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 equivalents they 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.: { CLR (r), DEC (r), INC (r), CPY ( r s , r d ), JZ (r, z), JE ( r j , r k , z ), J(z) } 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 JNZ Jump if Not Zero in place of JZ; yet another possible convenience instruction). ===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 (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 0 it has no indirection capability cannot 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 be by 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 times e.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. 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) that uses its finite-state machine to interpret a "program of instructions" located in its registers i.e. we are building what is nowadays called a computer with the von Neumann architecture. 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 approach runs into the same problem unless we allow instructions to have potentially unbounded size. So why not use a single "über-instruction" one massive number containing all the program instructions encoded within 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 bears little resemblance to 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' model quite similar to Melzak's (1961) model uses 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 indirection provide 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!). 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 s ] + (1-i)*r s 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 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: [r s1 ] + [r 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. 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 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 = [A] +1 → A Example: ADDA (r s ) = [A] + [r s ] → A Example: MULA (r s ) = [A] * [r 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 : { LDA (i/d, r s ), STA (i/d, r d ), CLRA, INCA, DECA, ADDA (r s ), SUBA (r s ), MULA (r s ), DIVA (r s ), etc.) LDAN (i/d) = CPY (i/d, N, d, A); LoaD Accumulator via iNdirection register STAN (i/d) = CPY (d, A, i/d, N). STore Accumulator via iNdirection register Why is this such an interesting approach? At least two reasons: (1) An instruction set with no parameters: Schönhage does this to produce his RAM0 instruction set. See section below. (2) Reduce a RAM to a Post-Turing machine: Posing as minimalists, we reduce all the registers excepting the accumulator A and indirection register N e.g. r = { r0, r1, r2, ... } to an unbounded string of (very-) bounded-capacity pigeon-holes. These will do nothing but hold (very-) bounded numbers e.g. a lone bit with value { 0, 1 }. Likewise we shrink the accumulator to a single bit. We restrict any arithmetic to the registers { A, N }, use indirect operations to pull the contents of registers into the accumulator and write 0 or 1 from the accumulator to a register: { LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I z ), JZ (I z ), H } We push further and eliminate A altogether by the use of two "constant" registers called "ERASE" and "PRINT": [ERASE]=0, [PRINT]=1. { CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I z ), JZ (I z ), H } Rename the COPY instructions and call INC (N) = RIGHT, DEC (N) = LEFT and we have the same instructions as the Post-Turing machine, plus an extra CLRN : { ERASE, PRINT, CLRN, RIGHT, LEFT, JZ (i, N, I z ), JZ (I z ), H } We give here a slightly more formal demonstration. Begin by designing our model with three reserved registers "E", "P", and "N", plus an unbounded set of registers 1, 2, ..., n to the right. The registers 1, 2, ..., n will be considered "the squares of the tape". Register "N" points to "the scanned square" that "the head" is currently observing. The "head" can be thought of as being in the conditional jump observe that it uses indirect addressing (cf Elgot-Robinson p. 398). As we decrement or increment "N" the (apparent) head will "move left" or "right" along the squares. We will move the contents of "E"=0 or "P"=1 to the "scanned square" as pointed to by N, using the indirect CPY. The fact that our tape is left-ended presents us with a minor problem: Whenever LEFT occurs our instructions will have to test to determine whether or not the contents of "N" is zero; if so we should leave its count at "0" (this is our choice as designers for example we might have the machine/model "trigger an event" of our choosing). Instruction set 1 (augmented): { INC (N), DEC (N), CLR (N), CPY (d, r s ,i, N), JZ ( i, r, z ), HALT } The following table both defines the Post-Turing instructions in terms of their RAM equivalent instructions and gives an example of their functioning. The (apparent)location of the head along the tape of registers r0-r5 . . . is shown shaded: Definition by cases CPY (i, q, d, φ) = def φ (q, r0, ..., rlast, y) = case_0: IF CLR (y), [q] - [y]=0 THEN CPY ( r0, φ ), J (exit) ELSE case_1: IF INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (exit) ELSE case_2 through case n: IF . . . THEN . . . ELSE case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (exit) ELSE case_n+1 to case_last: IF . . . THEN . . . ELSE case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (exit) ELSE default: woops Case_0 ( the base step of the recursion on y) looks like this: case_0: CLR ( y ) ; set register y = 0 JE ( q, y, _φ0 ) J ( case_1 ) _φ0: CPY ( r0, φ ) J ( exit ) case_1: etc. Case_n (the induction step) looks like this; remember, each instance of "n", "n+1", ..., "last" must be an explicit natural number: case_n: INC ( y ) JE ( q, y, _φn ) J ( case_n+1) _φn: CPY ( rn, φ ) J ( exit ) case__n+1: etc. Case_last stops the induction and bounds the CASE operator (and thereby bounds the "indirect copy" operator): case_last: INC ( y ) JE ( q, y, _φlast ) J ( woops ) _φlast: CPY ( rlast, φ ) J ( exit ) woops: how do we handle an out-of-bounds attempt? exit: etc. If the CASE could continue ad infinitum it would be the mu operator. But it can't its finite-state machine's "state register" has reached its maximum count (e.g. 65365 = 11111111,11111111 2 ) or its table has run out of instructions; it is a finite machine, after all. JEA ( r, z ) ; IF [A] = [r] then I z else continue INCA ; [A] + 1 --> A RAM0 model: Schönhage's RAM0 machine has 6 instructions indicated by a single letter (the 6th "C xxx" seems to involve 'skip over next parameter'. Schönhage designated the accumulator with "z", "N" with "n", etc. Rather than Schönhage's mnemonics we will use the mnemonics developed above. (Z), CLRA: 0 → A (A), INCA: [A] +1 → A (N), CPYAN: [A] → N (A), LDAA: A → A ; contents of A points to register address; put register's contents into A (S), STAN: [A] → [N] ; contents of N points to register address; put contents of A into register pointed to by N (C), JAZ ( z ): [A] = 0 then go to I z ; ambiguous in his treatment Indirection comes (i) from CPYAN (copy/transfer contents A to N) working with store_A_via_N STAN, and from (ii) the peculiar indirection instruction LDAA ( A → [A] ) . ==Footnotes== ==See also== Real RAM Transdichotomous model ==External links== Random Access Machine Emulator Random Access Machine Emulator Random Access Machine Emulator ==References== With a few exceptions, these references are the same as those at Register machine. Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. }. 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 recursion the other two. 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. . 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 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. . 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. . 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. 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 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, in: Jan van Leeuwen, 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 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378824699 under CC BY-SA 4.0; modifications have been made.