Counter Machine

The counter machine models go by a number of different names that may help to distinguish them by their peculiarities. In the following the instruction "JZDEC ( r )" is a compound instruction that tests to see if a register r is empty; if so then jump to instruction I_z, else if not then DECrement the contents of r:

• Shepherdson-Sturgis machine, because these authors formally stated their model in an easily accessible exposition (1963). Uses instruction set (1) augmented with additional convenience instructions ( JNZ is "Jump if Not Zero, used in place of JZ ):

{ INC ( r ), DEC ( r ), CLR ( r ), CPY ( r_j, r_k ), JNZ ( r, z ), J ( z ) }

• Minsky machine, because Marvin Minsky (1961) formalized the model. Usually uses instruction set (1), but instruction-execution is not default-sequential so the additional parameter 'z' appears to specify the next instruction after INC and as the alternative in JZDEC:

{ INC ( r, z ), JZDEC ( r, z_true, z_false) }

• Program machine, Program computer, the names Minsky (1967) gave the model because, like a computer its instructions proceed sequentially unless a conditional jump is successful. Uses (usually) instruction set (1) but may be augmented similar to the Shepherson-Sturgis model. JZDEC is often split apart:

{ INC ( r ), DEC ( r ), JZ ( r, z_true )}

• Abacus machine, the name Lambek (1961) gave to his simplification of the Melzak (1961) model, and what Boolos-Burgess-Jeffrey (2002) calls it. Uses instruction set (1) but with an additional parameter z to specify the next instruction in the manner of the Minsky (1961) model;

{ INC ( r, z ), JZDEC (r, z_true, z_false ) }

• Lambek machine, an alternative name Boolos-Burgess-Jeffrey (2002) gave to the abacus machine. Uses instruction set (1-reduced) with an additional parameter to specify the next instruction:

{ INC ( r, z ), JZDEC ( r, z_true, z_false ) }

• Successor machine, because it uses the 'successor operation' of, and closely resembles, the Peano axioms. Used as a base for the successor RAM model. Uses instruction set (2) by e.g. Schönhage as a base for his RAM0 and RAM1 models that lead to his pointer machine SMM model, also discussed briefly in van Emde Boas (1990):

• { CLR ( r ), INC ( r ), JE ( r_j, r_k, z ) }

• Elgot-Robinson model, used to define their RASP model (1964). This model requires one empty register at the start ( e.g. =0 ). (They augmented the same model with indirect addressing by use of an additional register to be used as an "index" register.)

{ INC (r), CPY ( r_s, r_d ), JE ( r_j, r_k, z ) }

• Other counter machines: Minsky (1967) demonstrates how to build the three base models (program/Minsky/Lambek-abacus, successor, and Elgot-Robinson) from the superset of available instructions described in the lead paragraph of this article. The Melzak (1961) model is quite different from the above because it includes 'add' and 'subtract' rather than 'increment' and 'decrement'. The proofs of Minsky (1961, 1967) that a single register will suffice for Turing equivalence requires the two instructions { MULtiply k, and DIV k } to encode and decode the Gödel number in the register that represents the computation. Minsky shows that if two or more registers are available then the simpler INC, DEC etc. are adequate (but the Gödel number is still required to demonstrate Turing equivalence; also demonstrated in Elgot-Robinson 1964 ).