Talk:Random access machine

From Wikipedia, the free encyclopedia

This seems to be a dupe of Register machine... -- 217.82.189.242 18:48, 1 Nov 2004 (UTC)

Per the comment above, indeed this definition does seem like that of a register machine. My bet is the definition is wrong. The register machine may or may not come with an infinite number of registers, but the registers are always infinite in size. I'll bet that the RAM has potentially infinite registers of finite size. I will research this in my travels through "abstact computer"-land and make the necessary changes. wvbaileyWvbailey 19:37, 11 September 2006 (UTC)

It appears that, unlike the register machine, the RAM (infinitely wide memory "registers" and either finite or infinite numbers of memory "registers") can experience "address computations", i.e. the memory is more or less indexed and "it is possible to take an address and add a value to it ... Referencing elements ... becomes a simple case of knowing the address of the first of the first element and then adding an offset to that address to get the desired element."

http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic2/

Like a register machine, all the computations occur "in the registers" (not in an "accumulator" or "accumulators").

So we (perhaps) have here a Post-Turing machine with a "tape" designed as a indexed random access memory instead of shift registers, the index register loadable/jammable by an instruction (?). Do we have direct addressing? We need more reference than this (to say the least). An offset implies a summation of a value in the register plus an the offset-value provided by the instruction. This is not the same as increment-decrement of the index register's value. And, other authors' (extremely vague) specifications don't seem to agree with this one. wvbaileyWvbailey 01:20, 12 September 2006 (UTC)

Contents

[edit] Definition of "Random access machine"

The defintion is going to be ambiguous.

[edit] Hopcroft and Ullman (1979)

From Hopcroft and Ullman (1979):

"In addition, abstract compter models, such as the random access machine (RAM), also give rise to the partial recursive functions.
"The RAM consists of an infinite number of memory words, numbered , 1, ..., each of which can hold any integer, and a finite number of arithmetic registers capable of holding any integer. Integers may be decoded into the usual sorts of computer instructions. We shall not define the RAM model more formally, but it should be clear that if we choose a suitable set of instructions, the RAM may simulate any existing computer" (p. 166)

Their RAM has a finite number of arithmetic registers each of which, like a register machine, can do arithmetic operations. There's a tape to hold each register's contents, a tape to hold the 'location counter', a tape to hold the 'memory address register' (cf their Theorem 7.6 p. 167)

Their proof uses:

"the first 10 bits of an instruction [to] denote one of the standard computer operations, such as LOAD, STORE, ADD, and so on, and the remaining bits denote the address of an operand" (p. 167)

Reference from Hopcroft and Ullman:

Cook, S. A. and Reckhow, R. A. (1973), Bounded random access machines," Journal of Computer and Systems Sciences 7:4, 354-375.

wvbaileyWvbailey 15:25, 14 September 2006 (UTC)

[edit] Melzak (1961)

In register machine we see Melzak turning his machine into something else by adding an "final modification", an "command" called "Ai Aj Ak":

"...this will allow the machine to change its own program in the process of carrying it out. Our modification consists essentially of introducing what is known in computer terminology as 'a computed go to' instruction" (p. 288)

The command Ai Aj Ak "operate[s] on certain locations fixed in advance, namely i, j, k." He then iterates i, j, k by letting these indices be an Ap, Aq, Ar. Written in a slighlty more friendly form"

A(Ap) A(Aq) A(Ar)

Not all the subscripts (Ap, Aq, Ar) are required. For example Ai, Aj, A(Ar) is permissible.

Suppose we have 8 holes, { A1, A2, A3, A4, A5, A6, A7, A8 }. Each contains an amount of pebbles: (< x> means "contents of hole x"): < A1 > = 5, < A2 > = 3, < A3 > = 7, all the rest contain zero:

{ 5, 2, 7, 0, 0, 0, 0, 0 }

The command : "S, A1, A(A3)" will do the following:

  • look in hole A1, see how many pebbles there are in it i.e. 5
  • remove this number (5 pebbles) from sink/source-hole S
  • look in hole A3, see how many pebbles there are in it i.e. 7
  • go to hole A7 and toss in the 5 pebbles i.e. 5 + 0 --> 5

The final result will be:

{ 5, 2, 7, 0, 0, 0, 5, 0 }

Suppose the next command is: "A3, A2, S" This will cause us to do the following:

  • look in hole A2, see how many pebbles there are in i.e. 2
  • attempt to remove this number from hole A3, i.e. 7 - 2 = 5 (is okay, so continue...)
  • put these 2 pebbles in sink/store S
{ 5, 2, 5, 0, 0, 0, 5, 0 }
We have just done: < A3 > - < A2 > --> < A3 >, i.e. 7 - 2 --> < A3 >

Now do the first command again, i.e. "S, A1, A(A3)"

  • look in hole A1, see how many pebbles there are in it i.e. 5
  • remove this number (5 pebbles) from sink/source S (but not from A1)
  • look in hole A3, see how many pebbles here are in it i.e. 5
  • go to hole A5 and toss in the pebbles i.e. 0 + 5 --> 5
{ 5, 2, 5, 0, 5, 0, 5, 0 }

The next time we do this we will cause A3 to become 0, and at this point we [might] have caused a jump (unclear whether the model's conditional jump is caused by 0 OR underflow, or just an attempt at underflow), probably doesn't matter.

Now we would have to convince ourselves that this model allows for a Turing machine formulation. Melzak proves that it does: "the details of constructing the simulation program are clear now [to him, maybe] and the program itself is left to the reader as an exercise." (p. 292)

In the last paragraph of the paper he observes that "there appears to be no easy way to arrange for a stored program" (p. 293). Which is the salient/key requirement for a RASP.

How to parse an instruction-list in "the holes":

(i) The machine would need a "program counter" hole (more likely a pair, whatever...) and an "instruction register" hole (more likely a pair... whatever). Upon receipt of "an instruction" pointed to by the "program counter" hole, the machine would put "the instruction" into the "instruction counter hole". [Either now or in a while it will have to reconstruct the now-missing instruction!]. (For example: 3 pebbles might be instruction "INCREMENT", 4 pebbles is "DECREMENT", IF-THEN's are an interesting challenge, etc).

(ii) Parsing: If the machine were to decrement its "instruction register-hole" (the instruction's opcode) until empty, the "empty-condition" would propel the next steps of the "fetch" toward one-of-many "instructions". For example: "If hole is zero do www ELSE", decrement hole, "If hole is zero" THEN jump to xxx ELSE", decrement hole, "If hole is zero THEN jump to yyy ELSE; Decrement hole; "IF hole is zero THEN jump to zzz ELSE"; Decrement hole; "IF hole is zero" THEN jump to 'error' ELSE; [jump to *-1]". After "the parse", the first thing a valid "instruction" would do would be to rebuild the emptied hole per its own number [increment hole, increment hole.... ]. After the rebuild, the decoded/parsed instruction send the machine to "execute" the chosen command.

(iii) We need the "indirect" ability to do this -- i.e. we need "pointer holes to 'the next instruction' ". wvbaileyWvbailey 23:55, 22 September 2006 (UTC)

[edit] Stephen A. Cook and Robert A. Reckhow (1973)

  • Cook, Stephen A. and Reckhow, Robert A. (1973),Time bounded random access machines," Journal of Computer and Systems Sciences 7:4, 354-375.

[edit] Random Access Machine model

Salient features: The "RAM" is a register machine with [additional specifications]: (ii) The "RAM" program cannot be modified, (iii) The "RAM" model specifies/allows indexing of registers [allows indexed moves].

  • Finite program
  • Infinite set of registers
  • Each register can hold an arbitrary integer: positive, zero, negative
  • Instructions are normally executed sequentially
  • All locations begin with 0's
  • Instructions start at instruction #1
  • Halts at line with no instructions or negative indirect address
  • Program cannot be modified.
*for ref. only: Fixed-Program Random Access Machine (RAM) Description
LOD (Xi, C) Xi <-- C, C any integer Move constant C into register Xi
ADD (Xi, Xj, Xk) Xi <-- Xj + Xk Add contents of register Xj to contents of register Xj and place in register Xi
SUB (Xi, Xj, Xk) Xi <-- Xj - Xk Subtract contents of register Xk from contents of register Xk and place in register Xi
MOVsi (Xi, Xj) Xi <-- X(Xj) Copy into Xi from source determined indirectly, i.e. contents of Xj is source register's address
MOVdi (Xi, Xj) X(Xi) <-- Xj Copy from Xj to destination determined indirectly, i.e. contents of Xj is destination-register's address
TRA (Xj, m) TRA m if Xj > 0 "Transfer" (jump) to instruction m if contents of register Xj > 0
RD (Xi) Read Xi Input into register Xi
PRI (Xi) Output j Output contents of register Xi

[edit] Stored Program Machine: Random Access Stored-Program machine model (RASP)

their reference [7]: Hartmanis, J. (1971), Computational Complexity of Random Access Stored Program Machines. Mathematical Systems Theory 5:3, pp. 232-245.

Salient features: The "RASP" is and is not a register machine: (i) the RASP has an "accumulator" and an "instruction counter" and all arithmetic operations occur in the accumulator (ii) The "RASP" program can be modified, (iii) The "RAM" model does NOT specify/allow indexing of registers.


  • Accumulator (AC)
  • AC holds an arbitrary [unbounded?] integer
  • Instruction counter (IC)
  • IC holds a non-negative integer
  • Infinite sequence of memory registers X0, X1, X2, ...
  • Each Xi can hold "an arbitrary [unbounded?] integer"
  • Instruction stored in two consecutive memory registers --
  • (i) operation code
  • (ii) parameter of the instruction
  • No indexing provided so RASP must modify its own program to access an unbounded number of registers
  • Normal" RASPs have finite instructions
  • First instruction appears in X0:X1
Mnemonic Opcode Random Access Program Machine (RASP) Description
LOD, j 1 AC <-- j, j any integer "Load" constant j into accumulator AC
ADD, j 2 AC <-- AC + < Xj > Add contents of register j to contents of accumulator and place in accumulator
SUB, j 3 AC <-- AC - < Xj > Subtract contents of register j from contents of accumulator and place in accumulator
STO, j 4 Xj <-- AC "Store " (copy) accumulator into register j
BPA, j 5 IF AC>0 then IC <-- j ELSE next instruction Branch on positive accumulator to instruction #j
RD , j 6 Read Xi Input into register Xi
PRI, j 7 Output Xi Output contents of register Xi
HLT ~(1 thru 7) HALT Stop, Halt

[edit] Hartmanis model of RAM and RASP

Their earliest reference is [1]: C.C.Elgot and A. Robinson, Random-access stored-program machines, an approach to programming languages, J. Assoc. Comput. Machin. 11 (1964), 365-399.

Context is complexity theory, in particular "time" (number of steps) to compute a particular function.

Their model under consideration is the random access stored program machine model or RASP. Salient features:

  • Memory and finite set of instructions RASP = < M, I >
  • Memory consists of "two special registers" Accumulator AC and Instruction register IC and an umbounded sequence of memory registers R1, R2, R3:
M = < AC, IC, R1, R2, R3, .... >
  • Memory registers R1, R2, R3, ... contain the program
  • Program begins at R1, i.e. the instruction register IC contains 1: < IC > = 1
  • Content of all unspecified registers is 0
  • Integers are encoded in binary
  • INPUT = a number placed into AC before the start
  • OUTPUT = an integer in AC after HALT
  • Each register is bounded: "capable of holding an arbitrary, finite-length binary string" (p.233)
  • Instructions "must include the HALT"
  • Three types of parameters available: n, written < n > or < Rn >, and << n >>
  • (1) Immediate -- a constant ADD 1, adds the number 1 to the contents of the accumulator: <AC> + 1 --> < AC >
  • (2) Direct -- the name/number of a register as in ADD <3> means add the contents of register #3 to the accumulator: < AC > + < 3 > --> < AC >
  • (3) Indirect -- the specified register Rn contains a number/name of another register. This other register is the source of the parameter.
R1-R8: { 3, 0, 7, 1, 5, 0, 0, 3 } then ADD << 8 >> means go to register #8. Find its contents. This number is 3. Now pull from this register #3 its number -- 7 -- and add to the accumulator. Thus register 4 is being used to "point to" another register. If we increment register #8 it will now contain the number "4". If we do a second indexed ADD: << 8 >> we go to #8, find the number "4", use this to specify the register R4, get its number = 1, and add this number 1 to the accumulator.

A RASP is Turing equivalent [their LEMMA]. A fixed program is one which does not change its own instructions: if it writes another program during execution but does not execute that program then it is a fixed program.

[edit] 1964: Calvin C. Elgot and Abraham Robinson define the RASP

  • Their references include [3] Hermes (1961), [6] Kaphengst (1959), [7] Wang (1957)

Their context is to "capture a model with the most salient features of the central processing unit of a modern digital computer". Also: non-modifying versus self-modifying programs.

So unless there is parallel independent work going on we are at the bottom of this. Their minimal instruction set (p. 379)

  • (1) S(x): add 1 to the contents of register x then next instruction in sequence [i.e. < x >+1 --> < x > ]
  • (2) D(x, y): copy/transfer contents of register x to register y then next instruction in sequence [i.e. < x > --> < y > & < x > --> < x >
  • (3) C(x, y, zzz): conditional transfer on equality:
IF < x > = < y > THEN instruction = zzz ELSE next instruction in sequence

[edit] article not properly referenced

Some citations of sources are not matched with a full reference (e.g. Boolos et al. in the "Formal Definition: Random Access Machine" section) Itayb 10:04, 21 March 2007 (UTC)

Had you looked under "References" you could have found them all at Register machine but since this is apparently not allowed on wickedpedia I added them all from there. And removed the template which should have been in the body of the article, under "references"... wvbaileyWvbailey 20:49, 22 March 2007 (UTC)