 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
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)[reply]
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."
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)[reply]
The defintion is going to be ambiguous.
From Hopcroft and Ullman (1979):
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:
Reference from Hopcroft and Ullman:
wvbaileyWvbailey 15:25, 14 September 2006 (UTC)[reply]
Inregister machine we see Melzak turning his machine into something else by adding an "final modification", an "command" called "Ai Aj Ak":
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"
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:
The command : "S, A1, A(A3)" will do the following:
The final result will be:
Suppose the next command is: "A3, A2, S" This will cause us to do the following:
Now do the first command again, i.e. "S, A1, A(A3)"
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)[reply]
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].
| *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 |
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.
| 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 |
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:
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.
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)
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)[reply]
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)[reply]
The citation: Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354-375. should be: S. A. Cook and R. A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences, 7(4):354 – 375, 1973. —Preceding unsigned comment added by Muondude (talk • contribs) 16:59, 6 May 2010 (UTC)[reply]
