Editing Random-access machine (section)

===Why the need for an indirect operation: Two major problems with the counter-machine model===
In the following one must remember that these models are abstract models with two fundamental differences from anything physically real: unbounded numbers of registers each with unbounded capacities. The problem appears most dramatically when one tries to use a counter-machine model to build a RASP that is [[Turing completeness|Turing equivalent]] and thus compute any partial [[mu recursive function]]:
* ''Melzak (1961) added indirection to his "hole-and-pebble" model so that his model could modify itself with a "computed goto" and provides two examples of its use ("Decimal representation in the scale of d" and "Sorting by magnitude", whether these are used in his proof that the model is Turing equivalent is unclear since "the program itself is left to the reader as an exercise" (p.&nbsp;292)). Minsky (1961, 1967) was able to demonstrate that, with suitable (but difficult-to-use) [[Gödel number]] encoding, the register model did not need indirection to be Turing equivalent; but it did need at least one unbounded register. As noted below, Minsky (1967) hints at the problem for a RASP but doesn't offer a solution. Elgot and Robinson (1964) proved that their RASP model P<sub>0</sub>{{spaced ndash}}it has no indirection capability{{spaced ndash}}cannot compute all "recursive sequential functions" (ones that have parameters of arbitrary length) if it does not have the capability of modifying its own instructions, but it can via Gödel numbers if it does (p.&nbsp;395-397; in particular figure 2 and footnote p.&nbsp;395). On the other hand their RASP model P'<sub>0</sub> equipped with an "index register" (indirect addressing) can compute all the "partial recursive sequential functions" (the mu recursive functions) (p.&nbsp;397-398).''
:''Cook and Reckhow (1973) say it most succinctly:''
::''The indirect instructions are necessary in order for a fixed program to access an unbounded number of registers as the inputs vary." (p. 73)''
* '''Unbounded ''capacities'' of registers versus bounded capacities of state-machine instructions''': The so-called ''finite'' state part of the machine is supposed to be{{spaced ndash}}by the normal definition of algorithm{{spaced ndash}}''very'' finite both in the number of "states" (instructions) and the instructions' sizes (their capacity to hold symbols/signs). So how does a state machine move an arbitrarily large constant directly into a register, e.g. MOVE (k, r) (Move constant k to register r)? If huge constants are necessary they must either start out in the registers themselves or be created by the state machine using a finite number of instructions e.g. multiply  and add subroutines using INC and DEC (but not a quasi-infinite number of these!).
::''Sometimes the constant k will be created by use of CLR ( r ) followed by INC ( r ) repeated k times{{spaced ndash}}e.g. to put the constant k=3 into register r, i.e. 3 → r, so at the end of the instruction [r]=3: CLR (r), INC (r), INC (r), INC (r). This trick is mentioned by Kleene (1952) p. 223. The problem arises when the number to be created exhausts the number of instructions available to the ''finite'' state machine; there is always a bigger constant than the number of instructions available to the ''finite'' state machine.''
* '''Unbounded ''numbers'' of registers versus bounded state-machine instructions''': This is more severe than the first problem. In particular, this problem arises when we attempt to build a so-called RASP, a "universal machine" (see more at [[Universal Turing machine]]) that uses its finite-state machine to interpret a "program of instructions" located in its registers{{spaced ndash}}i.e. we are building what is nowadays called a [[computer]] with the [[von Neumann architecture]].

:Observe that the counter machine's finite-state machine must call out a register ''explicitly'' (directly) by its name/number: INC (65,356) calls out register number "65,365" ''explicitly''. If the number of registers exceeds the capability of the ''finite'' state machine to address them, then registers outside the bounds will be unreachable. For example, if the finite-state machine can only reach 65,536 = 2<sup>16</sup> registers then how can it reach the 65,537th?

So how ''do'' we address a register beyond the bounds of the finite-state machine? One approach would be to modify the ''program''-instructions (the ones stored in the registers) so that they contain more than one command. But this too can be exhausted unless an instruction is of (potentially) unbounded size. So why not use just one "über-instruction"{{spaced ndash}}one really really big number{{spaced ndash}}that contains ''all'' the program instructions encoded into it! This is how Minsky solves the problem, but the [[Gödel number]]ing he uses represents a great inconvenience to the model, and the result is nothing at all like our intuitive notion of a "stored program computer".

Elgot and Robinson (1964) come to a similar conclusion with respect to a RASP that is "finitely determined". Indeed it can access an unbounded number of registers (e.g. to fetch instructions from them) but only if the RASP allows "self modification" of its ''program'' instructions, and has encoded its "data" in a Gödel number (Fig. 2 p. 396).

In the context of a more computer-like model using his RPT (repeat) instruction Minsky (1967) tantalizes us with a solution to the problem (cf p. 214, p. 259) but offers no firm resolution. He asserts:
:"In general a RPT operation could not be an instruction in the finite-state part of the machine ... this might exhaust any particular amount of storage allowed in the finite part of the computer [sic, his name for his RAM models]. RPT operations require infinite registers of their own." (p. 214).

He offers us a ''bounded'' RPT that together with CLR (r) and INC (r) can compute any [[primitive recursive function]], and he offers the unbounded RPT quoted above that as playing the role of μ operator; it together with CLR (r) and INC (r) can compute the mu recursive functions. But he does not discuss "indirection" or the RAM model per se.

From the references in Hartmanis (1971) it appears that Cook (in his lecture notes while at UC Berkeley, 1970) has firmed up the notion of indirect addressing. This becomes clearer in the paper of Cook and Reckhow (1973){{spaced ndash}}Cook is Reckhow's Master's thesis advisor. Hartmanis' model{{spaced ndash}}quite similar to Melzak's (1961) model{{spaced ndash}}uses two and three-register adds and subtracts and two parameter copies; Cook and Reckhow's model reduce the number of parameters (registers called out in the program instructions) to one call-out by use of an accumulator "AC".

'''The solution in a nutshell:''' Design our machine/model with unbounded '''indirection'''{{spaced ndash}}provide an ''unbounded'' "address" register that can potentially name (call out) any register no matter how many there are. For this to work, in general, the ''unbounded'' register requires an ability to be cleared and then incremented (and, possibly, decremented) by a potentially infinite loop. In this sense the solution represents the unbounded [[μ operator]] that can, if necessary, hunt ad infinitum along the unbounded string of registers until it finds what it is looking for. The pointer register is exactly like any other register with one exception: under the circumstances called "indirect addressing" it provides ''its'' contents, rather than the address-operand in the state machine's TABLE, to be the address of the target register (including possibly itself!).