Editing Register machine (section)

=== Elgot–Robinson (1964) and the problem of the RASP without indirect addressing ===
A RASP or random-access stored-program machine begins as a counter machine with its "program of instruction" placed in its "registers". Analogous to, but independent of, the finite state machine's "Instruction Register", at least one of the registers (nicknamed the "program counter" (PC)) and one or more "temporary" registers maintain a record of, and operate on, the current instruction's number. The finite state machine's TABLE of instructions is responsible for (i) fetching the current ''program'' instruction from the proper register, (ii) parsing the ''program'' instruction, (iii) fetching operands specified by the ''program'' instruction, and (iv) executing the ''program'' instruction.

Except there is a problem: If based on the ''counter machine'' chassis this computer-like, [[John von Neumann|von Neumann]] machine will not be Turing equivalent. It cannot compute everything that is computable. Intrinsically the model is bounded by the size of its (very-) ''finite'' state machine's instructions. The counter machine based RASP can compute any [[primitive recursive function]] (e.g. multiplication) but not all [[mu recursive function]]s (e.g. the [[Ackermann function]]).

Elgot–Robinson investigate the possibility of allowing their RASP model to "self modify" its program instructions.<ref name="Elgot-Robinson_1964"/> The idea was an old one, proposed by Burks–Goldstine–von Neumann (1946–1947),<ref name="Burks-Goldstine-Neumann_1947"/> and sometimes called "the computed goto". Melzak (1961)<ref name="Melzak_1961"/> specifically mentions the "computed goto" by name but instead provides his model with indirect addressing.

'''Computed goto:''' A RASP ''program'' of instructions that modifies the "goto address" in a conditional- or unconditional-jump ''program'' instruction.

But this does not solve the problem (unless one resorts to [[Gödel number]]s). What is necessary is a method to fetch the address of a program instruction that lies (far) "beyond/above" the upper bound of the ''finite'' state machine instruction register and TABLE.

:Example: A counter machine equipped with only four unbounded registers can e.g. multiply any two numbers ( m, n ) together to yield p—and thus be a primitive recursive function—no matter how large the numbers m and n; moreover, less than 20 instructions are required to do this! e.g. { 1: CLR ( p ), 2: JZ ( m, done ), 3 outer_loop: JZ ( n, done ), 4: CPY ( m, temp ), 5: inner_loop: JZ ( m, outer_loop ), 6: DEC ( m ), 7: INC ( p ), 8: J ( inner_loop ), 9: outer_loop: DEC ( n ), 10 J ( outer_loop ), HALT } However, with only 4 registers, this machine has not nearly big enough to build a RASP that can execute the multiply algorithm as a ''program''. No matter how big we build our finite state machine there will always be a ''program'' (including its parameters) which is larger. So by definition the bounded program machine that does not use unbounded encoding tricks such as Gödel numbers cannot be ''universal''.

Minsky (1967)<ref name="Minsky_1967"/> hints at the issue in his investigation of a counter machine (he calls them "program computer models") equipped with the instructions { CLR (r), INC (r), and RPT ("a" times the instructions m to n) }. He doesn't tell us how to fix the problem, but he does observe that:
: "''... the program computer has to have some way to keep track of how many RPT's remain to be done, and this might exhaust any particular amount of storage allowed in the finite part of the computer. RPT operations require infinite registers of their own, in general, and they must be treated differently from the other kinds of operations we have considered.''"<ref name="Minsky_1967"/>{{rp|page=214}}

But Elgot and Robinson solve the problem:<ref name="Elgot-Robinson_1964"/> They augment their P<sub>0</sub> RASP with an indexed set of instructions—a somewhat more complicated (but more flexible) form of indirect addressing. Their P'<sub>0</sub> model addresses the registers by adding the contents of the "base" register (specified in the instruction) to the "index" specified explicitly in the instruction (or vice versa, swapping "base" and "index"). Thus the indexing P'<sub>0</sub> instructions have one more parameter than the non-indexing P<sub>0</sub> instructions:
: Example: INC ( r<sub>base</sub>, index ) ; effective address will be [r<sub>base</sub>] + index, where the [[natural number]] "index" is derived from the finite-state machine instruction itself.