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 Iz, 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 ( rj, rk ), 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, ztrue, zfalse) }
  • 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, ztrue )}
  • 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, ztrue, zfalse ) }
  • 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, ztrue, zfalse ) }
  • 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 ( rj, rk, 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 ( rs, rd ), JE ( rj, rk, 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 ).

Read more about Counter Machine:  Formal Definition, Example: COPY The Count From Register #1 To #2, The Partial Recursive Functions: Building "convenience Instructions" Using Recursion, Problems With The Counter Machine Model, Two-counter Machines Are Turing Equivalent (with A Caveat)

Other articles related to "machine, counter machine, counter, machines":

Historical Development of The Register Machine Model - Elgot-Robinson (1964) and The Problem of The RASP Without Indirect Addressing
... A RASP or Random access stored program machine begins as a counter machine with its "program of instruction" placed in its "registers" ... Analogous to, but independent of, the finite state machine's "Instruction Register", at least one of the registers (nicknamed the "program counter" (PC)) and one or more "t ... The finite state machine's TABLE of instructions is responsible for (i) fetching the current program instruction from the proper register, (ii) parsing the ...
Counter Machine Reference Model
... The Counter machine's reference model is a set of choices and conventions to be used with the Counter machine and other model variants of the Register machine concept ...
Counter Machine Reference Model - Reference Library (RefLib) - Counter Machine Instructions
... The various Counter machine instruction sets are like "ultra-RISC instruction sets" ... And, as is the case for different RISC machine builders, even for very similar machines, different authors have used different instruction sets ... The "basic instructions" are used map these differences on the relevant Counter machine variant models ...
Algorithm Examples - Example: Counter-machine Versus Turing-machine Computation
... detailed than the above, because here the counter machine is specified to be a simulation in an EXCEL spread sheet ... similar, the core of the two algorithms is truly different in this example the counter machine has to increment "m" times its parameter "n" ... In the Turing machine case the machine just had to fill in the first blank it came to, then find its way "home" ...

Famous quotes containing the words machine and/or counter:

    The momentary charge at Balaklava, in obedience to a blundering command, proving what a perfect machine the soldier is, has, properly enough, been celebrated by a poet laureate; but the steady, and for the most part successful, charge of this man, for some years, against the legions of Slavery, in obedience to an infinitely higher command, is as much more memorable than that as an intelligent and conscientious man is superior to a machine. Do you think that that will go unsung?
    Henry David Thoreau (1817–1862)

    As deaths have accumulated I have begun to think of life and death as a set of balance scales. When one is young, the scale is heavily tipped toward the living. With the first death, the first consciousness of death, the counter scale begins to fall. Death by death, the scales shift weight until what was unthinkable becomes merely a matter of gravity and the fall into death becomes an easy step.
    Alison Hawthorne Deming (b. 1946)