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 ( rj, rk )" while preserving contents of rj in terms of the above:
{ CPY, CLR, J, DEC, INC, JZ, H }
The above is the instruction set of Shepherdson-Sturgis (1963).
  • Define "ADD ( rj, rk, ri )", (perhaps preserving the contents of rj, and rk ), by use of the above:
{ ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • Define " MULtiply ( rj, rk, ri )" (MUL) (perhaps preserving the contents of r1 r2), in terms of the above:
{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • Define "EXPonential ( rj, rk, ri )" (EXP) (perhaps preserving the contents of rj, rk ) 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.

Read more about this topic:  Counter Machine

Famous quotes containing the words instructions, convenience, partial and/or building:

    Realizing that his time was nearly spent, he gave full oral instructions about his burial and the manner in which he wished to be remembered.... A few minutes later, feeling very tired, he left the room, remarking, ‘I have no disposition to leave this precious circle. I love to be here surrounded by my family and friends.’ Then he gave them his blessing and said, ‘I am ready to go and I wish you goodnight.’
    —For the State of New Hampshire, U.S. public relief program (1935-1943)

    Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.
    Nadine Gordimer (b. 1923)

    The only coöperation which is commonly possible is exceedingly partial and superficial; and what little true coöperation there is, is as if it were not, being a harmony inaudible to men. If a man has faith, he will coöperate with equal faith everywhere; if he has not faith, he will continue to live like the rest of the world, whatever company he is joined to.
    Henry David Thoreau (1817–1862)

    I am not building here a statue to erect at the town crossroads, or in a church or a public square.... This is for a nook in a library, and to amuse a neighbor, a relative, a friend, who may take pleasure in associating and conversing with me.
    Michel de Montaigne (1533–1592)