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, I_z), JZ (I_z), 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, 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 }