Random-access Machine - Example: Bounded Indirection Yields A Machine That Is Not Turing Equivalent

Example: Bounded Indirection Yields A Machine That Is Not Turing Equivalent

Throughout this demonstration we have to keep in mind that the instructions in the finite state machine's TABLE is bounded, i.e. finite:

"Besides a merely being a finite set of rules which gives a seqeunce of operations for solving a specific type of problem, an algorithm has five important features " (italics added, Knuth p. 4-7).

The difficulty arises because the registers have explicit "names" (numbers) and our machine must call each out by name in order to "access" it.

We will build the indirect CPY ( i, q, d, φ ) with the CASE operator. The address of the target register will be specified by the contents of register "q"; once the CASE operator has determined what this number is, CPY will directly deposit the contents of the register with that number into register "φ". We will need an additional register that we will call "y" – it serves as an up-counter.

So the following is actually a constructive demonstration or proof that we can indeed simulate the indirect CPY ( i, q, d, φ ) without a "hardware" design change to our counter machine/model. However, note that because this indirect CPY is "bounded" by the size/extent of the finite state machine, a RASP using this indirect CPY can only calculate the primitive recursive functions, not the full suite of mu recursive functions.

The CASE "operator" is described in Kleene (1952) (p. 229) and in Boolos-Burgess-Jeffrey (2002) (p. 74); the latter authors emphasize its utility. The following definition is per Kleene but modified to reflect the familiar "IF-THEN-ELSE" construction.

The CASE operator "returns" a natural number into φ depending on which "case" is satisfied, starting with "case_0" and going successively through "case_last"; if no case is satisfied then the number called "default" (aka "woops") is returned into φ (here x designates some selection of parameters, e.g. register q and the string r0, ... rlast )):

Definition by cases φ (x, y):

• case_0: IF Q₀(x, y) is true THEN φ₀(x, y) ELSE
• case_1: IF Q₁(x, y) is true THEN φ₁(x, y) ELSE
• cases_2 through case_next_to_last: etc. . . . . . . . . ELSE
• case_last: IF Q_last(x, y) is true THEN φ_last(x, y) ELSE
• default: do φ_default(x, y)

Kleene require that the "predicates" Q_n that doing the testing are all mutually exclusive – "predicates" are functions that produce only { true, false } for output; Boolos-Burgess-Jeffrey add the requirement that the cases are "exhaustive".

We begin with a number in register q that represents the address of the target register. But what is this number? The "predicates" will test it to find out, one trial after another: JE (q, y, z) followed by INC (y). Once the number is identified explicitly, the CASE operator directly/explicitly copies the contents of this register to φ:

Definition by cases CPY (i, q, d, φ) =_def φ (q, r0, ..., rlast, y) =

• case_0: IF CLR (y), - =0 THEN CPY ( r0, φ ), J (exit) ELSE
• case_1: IF INC (y), = =1 THEN CPY ( r1, φ ), J (exit) ELSE
• case_2 through case n: IF . . . THEN . . . ELSE
• case_n: IF INC (y), = =n THEN CPY ( rn, φ ), J (exit) ELSE
• case_n+1 to case_last: IF . . . THEN . . . ELSE
• case_last: IF INC (y), = ="last" THEN CPY ( rlast, φ ), J (exit) ELSE
• default: woops

Case_0 ( the base step of the recursion on y) looks like this:

• case_0:

• CLR ( y ) ; set register y = 0
• JE ( q, y, _φ0 )
• J ( case_1 )

• _φ0: CPY ( r0, φ )
• J ( exit )

• case_1: etc.

Case_n (the induction step) looks like this; remember, each instance of "n", "n+1", ..., "last" must be an explicit natural number:

• case_n:

• INC ( y )
• JE ( q, y, _φn )
• J ( case_n+1)

• _φn: CPY ( rn, φ )
• J ( exit )

• case__n+1: etc.

Case_last stops the induction and bounds the CASE operator (and thereby bounds the "indirect copy" operator):

• case_last:

• INC ( y )
• JE ( q, y, _φlast )
• J ( woops )

• _φlast: CPY ( rlast, φ )
• J ( exit )

• woops: how do we handle an out-of-bounds attempt?
• exit: etc.

If the CASE could continue ad infinitum it would be the mu operator. But it can't – its finite state machine's "state register" has reached its maximum count (e.g. 65365 = 11111111,11111111₂ ) or its table has run out of instructions; it is a finite machine, after all.