Counter Machine - The Partial Recursive Functions: Building "convenience Instructions" Using Recursion

The Partial Recursive Functions: Building "convenience Instructions" Using Recursion

The example above demonstrates how the first basic instructions { INC, DEC, JZ } can create three more instructions -- unconditional jump J, CLR, CPY. In a sense CPY used both CLR and J plus the base set. If register #3 had had contents initially, the sum of contents of #2 and #3 would have ended up in #3. So to be fully accurate CPY program should have preceded its moves with CLR (1) and CLR (2).

However, we do see that ADD would have been possible, easily. And in fact the following is summary of how the primitive recursive functions such as ADD, MULtiply and EXPonent can come about (see Boolos-Burgess-Jeffrey (2002) p. 45-51).

• Beginning instruction set: { DEC, INC, JZ, H }
• Define unconditional "Jump J (z)" in terms of JZ ( r0, z ) given that r0 contains 0.

{ J, DEC, INC, JZ, H }

• Define "CLeaR ( r ) in terms of the above:

{ CLR, J, DEC, INC, JZ, H }

• Define "CoPY ( r_j, r_k )" while preserving contents of r_j in terms of the above:

{ CPY, CLR, J, DEC, INC, JZ, H }

The above is the instruction set of Shepherdson-Sturgis (1963).

• Define "ADD ( r_j, r_k, r_i )", (perhaps preserving the contents of r_j, and r_k ), by use of the above:

{ ADD, CPY, CLR, J, DEC, INC, JZ, H }

• Define " MULtiply ( r_j, r_k, r_i )" (MUL) (perhaps preserving the contents of r1 r2), in terms of the above:

{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

• Define "EXPonential ( r_j, r_k, r_i )" (EXP) (perhaps preserving the contents of r_j, r_k ) in terms of the above,

{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

In general, we can build any partial- or total- primitive recursive function that we wish, by using the same methods. Indeed Minsky (1967), Shepherdson-Sturgis (1963) and Boolos-Burgess-Jeffrey (2002) give demonstrations of how to form the five primitive recursive function "operators" (1-5 below) from the base set (1).

But what about full Turing equivalence? We need to add the sixth operator -- the μ operator -- to obtain the full equivalence, capable of creating the total- and partial- recursive functions:

1. Zero function (or constant function)
2. Successor function
3. Identity function
4. Composition function
5. Primitive recursion (induction)
6. μ operator (unbounded search operator)

The authors show that this is done easily within any of the available base sets (1, 2, or 3) (an example can be found at μ operator ). However, the reader needs to be cautioned that, even though the μ operator is easily created by the base instruction set doesn't mean that an arbitrary partial recursive function can be easily created with a base model -- Turing equivalence and partial recursive functions imply an unbounded μ operator, one that can scurry to the ends of the register chain ad infinitum searching for its goal. The problem is: registers must be called out explicily by number/name e.g. INC (47,528) and DEC (39,347) and this will exhaust the finite state machine's TABLE of instructions. No matter how "big" the finite state machine is, we can find a function that uses a "bigger" number of registers.