Footnotes
Footnote|Successor model:
Some readers may argue that the "successor model" -- counter machine with instructions, where "JE" means "Jump if Equal", i.e.
- { CLR (r), INC(r), JE (rj, rk, z) }
is "more basic", because it closely resembles the Peano axioms and the operators of the primitive recursive functions. Indeed the model can be found in Minsky (1967) (p. 192ff) in his discussion of a Turing equivalent set of operators called the McCarthy Formalism.
Minsky shows how to derive DEC (r) from the three-instruction successor-set (cf. p. 211) -- JZ is trivial --and he proceeds to use this second model in his discussion of its equivalence to the primitive recursive functions and the general-recursive functions (cf p. 212ff).
With this "successor" set the problem of the first set { INC, DEC, JZ } around what happens when DEC occurs on an empty register does not occur; however, the model requires JE to have a 3-parameter format: JE(r1, r2, z).
Formal Syntax:
- In the following, the letter "r" will be put in front of a register number e.g. r0 in place of "0" to avoid confusion of "zero" with the register named "0", for example to avoid ambiguous symbolism such as "0 → 3". "z" is a number of an instruction Iz.
| Instruction | Effect on register | Effect on state-machine's Instruction Counter Register ICR |
| CLR ( r ) | 0 → r | + 1 → IR |
| INC ( r ) | + 1 → r | + 1 → IR |
| JE ( rj, rk, z) | If = THEN z → IR ELSE + 1 → IR |
The following shows how the successor set { CLR (r), INC (r), JE (rj, rk, z) } creates the instruction set { INC (r), DEC (r), JZ (r, z) }. A similar treatment can be found in Minsky (p. 211) excepting that Minsky uses JNE -- Jump if Not Equal --rather than JE.
- (1) INC (r) is the same for both sets.
- (2) JZ (rk, z) = JE (r0, rk, z) ; contents of register "r0" must be 0
- (3) DEC (r5) requires the use of two scratch-pad registers #r2 & #r3. The algorithm proceeds by first clearing a scratch pad and testing input #r5 for 0, then (ii) clearing scratchpad #r3 and then, while contents of #r2 ≠ contents of #r5, incrementing #r2 so that #r3 is always one behind #r3, (iii) when #r2 is equal to #r5 (#r3 is one less than both), then clearing #r5 and copying #r3 back into #r5, (v) cleaning up the mess leaving only #r5 with contents.
NOTE: In the following example of "DEC (r5), rather than use a "free_variable" such as "r", we declare explicit register #r5. This emphasizes the point that each instance of DEC must be built separately with its own explicit register declared. This is because "DEC (r5)" is not "calling a subroutine" called DEC and "passing 5" to it, but rather "DEC (r5)" is its own little piece of 14-line "code" to be inserted (by hand or compiler) wherever it is desired (DEC (r4) would be its own piece of code, etc). This example emphasizes the fact that, once fixed, an instruction set such as { CLR, INC, JE } for a counter machine specifies hardware of the state machine, not "software patches". In the case of a RAM or RASP, indirect addressing would allow for true subroutines.
| Label: | Instr. #: | Instruction: | Formal equivalence: | Comment |
| DEC (5): | target register #5 contains n or 0 | |||
| initialize: | 1 | CLR (r2) | 0 → r2 | clear scratch-pad register #r2 |
| test_for zero: | r2 | JE (r5,r2,13) | If = then 13 → IR else +1 → ICR | If contents of target register=0 then done |
| 3 | CLR (r3) | Ø → r3 | clear scratch-pad register #3 | |
| increment_loop: | 4 | INC (r2) | +1 → 2 | Increment register #2 until contents of #2= contents of #5 |
| 5 | JE (r5,r2,8) | If = then 8→ IR else +1 → IR | ||
| 6 | INC (r3) | +1 → r3 | Contents of #3 will be one less than contents of #2 | |
| 7 | JE (r5,r5,4) | If = then 4 → ICR else +1 = ICR | Unconditional jump | |
| move(3,1): | ||||
| 8 | CLR (r5) | 0 → r5 | clear target register #5 | |
| move(3,1)_loop: | 9 | JE (r5,r3, 12) | If = then 12 → IR else +1 → IR | clear scratch-pad register #2 |
| 10 | INC (r5) | +1 → r5 | Increment contents of register #5 | |
| 11 | JE (r5,r5,9) | If = then 9→ IR else +1 → IR | Unconditional jump to instruction 9 | |
| 12 | JE (r5,r5,10) | If = then 10 → IR else +1 → IR | Unconditional jump to instruction 10 | |
| 13 | CLR (r2) | 0 → r2 | clear scratch-pad register #2 | |
| clean_up: | 14 | CLR (r3) | 0 → r3 | clear scratch-pad register #3 |
| done: | 15 | etc. | etc. | target register #5 contains n-1 or Ø |
Footnote|IF-THEN-ELSE operator:
From Minsky (1967):
- " f = (if p1 then e1 else e1)
- "This expression means
- "See if p1 is true; if so the value of f is given by e1. If p1 is false, the value of f is given by e2." (Minsky 1967 pp. 192ff: Conditional Expressions; The McCarthy Formalism)
This type of operator can also be found as the CASE function defined in Kleene (1952) p. 229 #F ("mutually-exclusive predicates").
Read more about this topic: Counter Machine Reference Model