Random-access Machine - The Notion of Indirect Address Register "N"

The Notion of Indirect Address Register "N"

If our model has an unbounded accumulator can we bound all the other registers? Not until we provide for at least one unbounded register from which we derive our indirect addresses.

The minimimalist approach is to use itself (Schönhage does this).

Another approach (Schönhage does this too) is to declare a specific register the "indirect address register" and confine indirection relative to this register (Schonhage's RAM0 model uses both A and N registers for indirect as well as direct instructions). Again our new register has no conventional name – perhaps "N" from "iNdex", or "iNdirect" or "address Number".

For maximum flexibility, as we have done for the accumulator A – we will consider N just another register subject to increment, decrement, clear, test, direct copy, etc. Again we can shrink the instruction to a single-parameter that provides for direction and indirection, for example.

LDAN (i/d) = CPY (i/d, N, d, A); LoaD Accumulator via iNdirection register
STAN (i/d) = CPY (d, A, i/d, N). STore Accumlator 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, Iz), JZ (Iz), H }

We push further and eliminate A altogether by the use of two "constant" registers called "ERASE" and "PRINT": =0, =1.

{ CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, Iz), JZ (Iz), 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, Iz), JZ (Iz), H }

Read more about this topic:  Random-access Machine

Famous quotes containing the words notion, indirect, address and/or register:

    The notion of some infinitely gentle
    Infinitely suffering thing.
    —T.S. (Thomas Stearns)

    Long as I have lived, and many blasphemers as I have heard and seen, I have never yet heard or witnessed any direct and conscious blasphemy or irreverence; but of indirect and habitual, enough. Where is the man who is guilty of direct and personal insolence to Him that made him?
    Henry David Thoreau (1817–1862)

    I believe the alphabet is no longer considered an essential piece of equipment for traveling through life. In my day it was the keystone to knowledge. You learned the alphabet as you learned to count to ten, as you learned “Now I lay me” and the Lord’s Prayer and your father’s and mother’s name and address and telephone number, all in case you were lost.
    Eudora Welty (b. 1909)

    A funeral is not death, any more than baptism is birth or marriage union. All three are the clumsy devices, coming now too late, now too early, by which Society would register the quick motions of man.
    —E.M. (Edward Morgan)