Turing Equivalence of The RAM With Indirection
In the section above we informally showed that a RAM with an unbounded indirection capability produces a Post-Turing machine. The Post-Turing machine is Turing equivalent, so we have shown that the RAM with indirection is Turing equivalent.
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, rs,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:
| Mnemonic | label: | E | P | N | r0 | r1 | r2 | r3 | r4 | r5 | etc. | Action on registers | Action on finite state machine Instruction Register IR | |||
| start: | 0 | 1 | 3 | 1 | 0 | |||||||||||
| R | right: | INC ( N ) | 0 | 1 | 4 | 1 | 0 | +1 → N | +1 → IR | |||||||
| P | print: | CPY ( d, P, i, N ) | 0 | 1 | 4 | 1 | 1 | =1 → =r4 | +1 → IR | |||||||
| E | erase: | CPY ( d, E, i, N ) | 0 | 1 | 4 | 1 | 0 | =0 → =r4 | +1 → IR | |||||||
| L | left: | JZ ( i, N, end ) | 0 | 1 | 4 | 1 | 0 | none | IF N =r4] =0 THEN "end" → IR else +1 → IR | |||||||
| DEC ( N ) | 0 | 1 | 3 | 1 | 0 | -1 → N | ||||||||||
| J0 ( halt ) | jump_if_blank: | JZ ( i, N, end ) | 0 | 1 | 3 | 1 | 0 | none | IF N =r3] =0 THEN "end" → IR else +1 → IR | |||||||
| J1 ( halt ) | jump_if_mark: | JZ ( i, N, halt ) | 0 | 1 | 3 | 1 | 0 | N =r3] → A | IF N =r3] =0 THEN "end" → IR else +1 → IR | |||||||
| end | . . . etc. | 0 | 1 | 3 | 1 | 0 | ||||||||||
| halt: | H | 0 | 1 | 3 | 1 | 0 | none | +1 → IR |
Read more about this topic: Random-access Machine
Famous quotes containing the word ram:
“At one time or another, almost every politician needs an honest man so badly that, like a ravenous wolf, he breaks into a sheep-fold: not to devour the ram he has stolen, however, but rather to conceal himself behind its wooly back.”
—Friedrich Nietzsche (1844–1900)