Editing Random-access machine (section)

=== Bounded indirection and the primitive recursive functions ===
If we eschew the Minsky approach of one monster number in one register, and specify that our machine model will be "like a computer" we have to confront this problem of indirection if we are to compute the recursive functions (also called the [[μ-recursive function]]s ){{spaced ndash}}both total and partial varieties.

Our simpler counter-machine model can do a "bounded" form of indirection{{spaced ndash}}and thereby compute the sub-class of [[primitive recursive function]]s{{spaced ndash}}by using a primitive recursive "operator" called "definition by cases" (defined in Kleene (1952) p. 229 and Boolos-Burgess-Jeffrey p. 74). Such a "bounded indirection" is a laborious, tedious affair. "Definition by cases" requires the machine to determine/distinguish the contents of the pointer register by attempting, time after time until success, to match this contents against a number/name that the case operator ''explicitly'' declares. Thus the definition by cases starts from e.g. the lower bound address and continues ad nauseam toward the upper bound address attempting to make a match:
: ''Is the number in register N equal to 0? If not then is it equal to 1? 2? 3? ... 65364? If not then we're at the last number 65365 and this had better be the one, else we have a problem!''

"Bounded" indirection will not allow us to compute the partial recursive functions{{spaced ndash}}for those we need ''unbounded'' indirection aka the [[μ operator]].
:''Suppose we had been able to continue on to number 65367, and in fact that register had what we were looking for. Then we could have completed our calculation successfully! But suppose 65367 didn't have what we needed. How far should we continue to go?''

To be [[Turing completeness|Turing equivalent]] the counter machine needs to either use the unfortunate single-register Minsky [[Gödel number]] method, or be augmented with an ability to explore the ends of its register string, ad infinitum if necessary. (A failure to find something "out there" defines what it means for an algorithm to fail to terminate; cf Kleene (1952) pp. 316ff ''Chapter XII Partial Recursive Functions'', in particular p. 323-325.) See more on this in the example below.