Introduction
In counter machine models the reader will observe, and may be bewildered by, the plethora of instruction sets defined by their authors. This reference will use the symbolism defined below to provide a standarized presentation format (syntax) to facilitate comparison of the sets and help give them definition.

The base model is derived from Minsky (1967), Lambek (1961) and in particular Shepherdson-Sturgis (1963 p. 225).


[edit] Formal Definition
The Counter machine reference model consists of a finite set of registers r1 ... rn, each of which can hold a non-negative integer, r0 (always zero), and a finite list of instructions I1 ... Im. Each of the instructions in this list is one of the following:

INC(j) — increment the value of register rj by 1; go to the successor instruction (e.g. instruction that is numerically next-in-sequence).
DEC(j) — If the contents of r is not 0 (not empty) then decrement the value of register rj by 1, else the contents of r=0; go to the successor instruction.
JZ (j, z) — If the contents of register rj equals Zero then Jump to instruction Iz else go to the successor instruction.
HALT — halts the computation.
Formal Semantic:

Instruction Effect on register Effect on Instruction Counter (IC)
INC ( j ) [ j ] + 1 → j [IC] + 1 → IC
DEC ( j ) IF [ j ] > 0 THEN [ j ] - 1 → j ELSE 0 → j [ IC ] + 1 → IC
JZ ( j, z ) IF [ j ] =0 THEN Iz → IC ELSE [ IC ] + 1 ) → IC


[edit] Reference Library (RefLib)
The "Counter machine reference model" library, or RefLib, is a set of conventions chosen to:

Specify the "instruction labels";
Specify the syntax (effective symbol-strings) of these labels;
Specify the semantics (meaning, content) of the labels and demonstrate equivalences.
Through the RefLib other instruction sets from similar register machine models can be emulated. In a sense the new instructions become "subroutines" of the "base" instructions -- Shepherdson-Sturgis (1963) used this stratgy in their demonstration that the three base instructions form a set that is equivalent to the primitive recursive functions. The RefLib may be seen also as a microcoded implementation strategy: the same counter machine is augmented by new instructions from instruction set; it is not a new machine.

The RefLib scripts (instruction implementations) are "near to formal". For a precise demonstration imagine the use of a C preprocessor to expand the RefLib script templates into standard instructions.


[edit] 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.

Emulated instruction Implementation (script) Comments
J (i) JZ (r0,i)
Go to i (unconditional jump); register #0 must contain 0.
JZ(rX, i1,i2) JZ (rX,i1)
JZ (r0,i2)
IF rX=0 THEN i1 ELSE i2
DECJZ(r,i) JZ (r,*i)
DEC(r)
Test r=0; if r = 0 then DEC
INCJ(r,i) INC(r)
J (i)
INC and J.
CLR(r) JZ (r,*+3)
DEC(r)
J (*-2)
If r=0 goto *+3; if not then DEC and goto *-2
MOV(rX,rY) 1 CLR(rY)
2 JZ (rX,*+4)
3 INC(rY)
4 DEC(rX)
5 J (*-4)
6 CONTINUE
Move rX to rY, clearing contents of rX.
CPY(rX,rY) 1 CLR(rY) 9 JZ (rW,13)
2 CLR(rW) 10 INC(rX)
3 JZ (rX,8) 11 DEC(rW)
4 INC(rY) 12 J (9)
5 INC(rW) 13 CONTINUE
6 DEC(rX)
7 J (3)
8 ??
Copy rX into rY, rW must be free (at end rW=0).
CPY (k,r) CLR (r)
( INC (r) )k
Immediate (explicit) copy constant k from instructions into R: Clear R and ( INC(r) )1 ,..., ( INC(r) )k i.e. do k times. Alternatively: put constant in register #K: CPY (K, r1)
CMP(rX,rY,r) 1 CPY(rX,r) 6 JZ(r0,3)
2 CPY(rY,rW) 7 JZ(rW,9)
3 JZ(r,7) 8 INC(r)
4 DEC(r) 9 CONTINUE
5 DEC(rW)
Compare rX with rY and returns on r (r=0 if rX equal rY).
ADD(rX,rX,r) ... in terms of JZ, DEC, J, CLR, INC, CPY. r=rX+rY; perhaps preserving the contents of rX and rY.
MUL(rX,rY,r) ... in terms of JZ, DEC, J, CLR, INC, CPY, ADD. MULtiply, r=rX*rY; perhaps preserving the contents of rX and rY.
SUB(rX,rY,r) ... in terms of ... SUBtract, r=rX-rY; perhaps preserving the contents of rX and rY.


[edit] Complex instructions
The Counter machine analysis on instruction sets preceded, and was a "theoretical laboratory" for, the RISC vs CISC features.

Many authors have augmented the basic counter machine model instruction set, with a more complex instructions, for this kind of studies.

Emulated instruction Implementation (script) Comments
EXP(rX,rY,r) ... in terms of JZ, DEC, J, CLR, INC, CPY, ADD, MUL. EXPonential, r=rX**rY; perhaps preserving the contents of rX and rY.
... ... other "complex instrucions".


[edit] Overloading
See T...

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. It permits comparisons between models, and serves a didactic function with regards to examples and descriptions.

It is based on conventional models, labels and terminology. The reference (base) model is intended to preserve consistency between articles.