Counter-machine model

There are many variants of the counter machine, among them those of Hermes, Ershov, Péter, Minsky, Lambek, Shepherdson and Sturgis, and Schönhage. These are explained below.

The models in more detail

1954: Hermes' model

observe that "the proof of this universality ... seems to have been first written down by Hermes, who showed in how an idealized computer could be programmed to duplicate the behavior of any Turing machine", and: "Kaphengst's approach is interesting in that it gives a direct proof of the universality of present-day digital computers, at least when idealized to the extent of admitting an infinity of storage registers each capable of storing arbitrarily long words".
The only two arithmetic instructions are

Successor operation
Testing two numbers for equality

The rest of the operations are transfers from register-to-accumulator or accumulator-to-register or test-jumps.
Kaphengst's paper is written in German; Sheperdson and Sturgis' translation uses terms such as "mill" and "orders".
The machine contains "a mill". Kaphengst designates his mill/accumulator with the "infinity" symbol but we will use "A" in the following description. It also contains an "order register". The order/instruction register is register "0". And, although not clear from Sheperdson and Sturgis' exposition, the model contains an "extension register" designated by Kaphengst "infinity-prime"; we will use "E".
The instructions are stored in the registers:
Thus this model is actually a random-access machine. In the following, "" indicates "contents of" register r, etc.

		Action:	Description
D1:	C	→ A, → r	Copy contents of register r to accumulator A
D2:	C	→ r, → A	Copy contents of accumulator A to register r
C1:	O	0 → A	Zero accumulator A
A1:	P	+ 1 → A	Increment contents of accumulator A
F1:		IF = 0 THEN jump to "Exit 1"	Jump if contents of accumulator A = 0
G1:	On	IF = THEN 0 → < A > ELSE 1 → A	Clear contents of A if contents of A = contents of r, else "set" A=1
G2:	O'	1 → A	"Set" contents of A = 1

remove the mill/accumulator A and reduce the Kaphengst instructions to register-to-register "copy", arithmetic operation "increment", and "register-to-register compare". Observe that there is no decrement. This model, almost verbatim, is to be found in ; see more in the section below.

		Action:	Description:
a:	P	+ 1 → A	Increment contents of accumulator A
d.	C	→ r_k, → r_j	Copy contents of register r_j to register r_k
f:	J	IF = 0 THEN jump to "Exit 1" ELSE next instruction	Jump if contents of register r = 0
c:	E	IF = THEN 0 → E ELSE 1 → E	Clear contents of register E if contents of r_j = contents of r_k, else "set" E=1

1958: Ershov's class of operator algorithms

observe that Ersov's model allows for storage of the program in the registers. They assert that Ersov's model is as follows:

		Action:	Description:
d.	C	→ r_k, → r_j	Copy contents of register r_j to register r_k
d'.	C'	+1 → r_k, → r_j	Copy incremented contents of register r_j to register r_k
e.	J	Jump to "Exit 1"	Unconditional jump to "Exit #1"
f*:		IF ≤ THEN jump to "Exit 1" ELSE jump to "Exit 2"	Jump to exit E1 if contents of register r_j is less than or equal to contents of r_k, else jump to E=2

1958: Péter's "treatment"

observe that Péter's "treatment" has an equivalence to the instructions shown in the following table. They comment specifically about these instructions, that:

		Action:	Description:
c:	O	0 →	Zero register n
d.	C	→ n, →	Copy contents of register m to register n
d'.	C'	+ 1 → , →	Copy incremented contents of register m to register n
e.	J	IF = jump to E1 ELSE jump to E2	Conditional jump to E1 if contents of m equals contents of n, else jump to E2.

1961: Minsky's model of a partial recursive function reduced to a "program" of only two instructions

In his inquiry into problems of Emil Post and Hilbert's 10th problem led Minsky to the following definition of:
His "Theorem Ia" asserts that any partial recursive function is represented by "a program operating on two integers S1 and S2 using instructions Ij of the forms:

		Action:	Description:
a.	ADD	+ 1 → r; go to instruction I_j1.	Increment contents of register r and go to instruction I_j1.
b.		If ≤ 0 THEN go to instr. I_j2 ELSE -1 → r and go to instr. I_j1	IF contents of register r equals zero THEN jump to instruction I_j2; ELSE decrement contents of register r and jump to instr. I_j1.

The first theorem is the context of a second "Theorem IIa" that

		Action:	Description:
a.	MULT	*K_j → r1; go to instruction I_j1.	Multiply contents of register r1 by constant K_j
b.		/Kj = 0 then go to instruction I_j2 else go to I_j1.	If division of contents of register 1 by constant K_j has no remainder then instr. I_j1 else instr. I_j2

In this second form the machine uses Gödel numbers to process "the integer S". He asserts that the first machine/model does not need to do this if it has 4 registers available to it.

1961: Melzak model: a single ternary instruction with addition and proper subtraction

If we use the context of his model, "keeping tally" means "adding by successive increments" or "subtracting by successive decrements"; transferring means moving the contents from hole A to hole B, and comparing numbers is self-evident. This appears to be a blend of the three base models.
Melzak's physical model is holes in the ground together with an unlimited supply of pebbles in a special hole S.
The instruction is a single "ternary operation" he calls "XYZ":
Of all the possible operations, some are not allowed, as shown in the table below:

Allowed	Instruction	Hole "X"	Hole "Y"	Hole "Z"	Meaning of Instruction
NO	XXX
	XXY	=0 → X	+ → Y	→ Z	All of X's pebbles taken from X and added to Y
	XXS	=0 → X	→ Y	→ Z	All of X's pebbles taken from X and put into sink/source S
NO	XYX
	XYY	- → X	+ → Y	→ Z	Count of Y's pebbles taken from X and placed in Y, doubling count of Y
	XYS
NO	XSX
NO	XSY
NO	XSS
	XYZ	- → X	→ Y	+ → Z	Count of Y's pebbles taken from X and added to Z,
	SYY	→ X	+ → Y	→ Z	Count of Y's pebbles taken from S and added to Y, doubling Y's count
	SYZ	→ X	→ Y	+ →	Count of Y's pebbles taken from S and added to Z

Some observations about the Melzak model:

1961: Lambek "abacus" model: atomizing Melzak's model to X+, X- with test

Original "abacus" model of Lambek :
Lambek references Melzak's paper. He atomizes Melzak's single 3-parameter operation into a 2-parameter increment "X+" and 3-parameter decrement "X-". He also provides both an informal and formal definition of "a program". This form is virtually identical to the Minsky model, and has been adopted by.

		Action:	Description:
a.	X+	+ 1 → r; go to instruction I_a.	Increment contents of register r
b.	X-	If ≤ 0, go to instr.I_b else -1 → r and go to instr. I_a	First test for zero, then decrement contents of register r

Abacus model of Boolos, Burgess & Jeffrey:
The various editions beginning with 1970 the authors use the Lambek model of an "infinite abacus". This series of Wikipedia articles is using their symbolism, e.g. " +1 → r" "the contents of register identified as number 'r', plus 1, replaces the contents of register number 'r' ".
They use Lambek's name "abacus" but follow Melzak's pebble-in-holes model, modified by them to a 'stones-in-boxes' model. Like the original abacus model of Lambek, their model retains the Minsky use of non-sequential instructionsunlike the "conventional" computer-like default sequential instruction execution, the next instruction I_a is contained within the instruction.
Observe, however, that B-B and B-B-J do not use a variable "X" in the mnemonics with a specifying parameter --i.e. "X+" and "X-"but rather the instruction mnemonics specifies the registers themselves, e.g. "2+", or "3-":

		Action:	Description:
a1.	1+	+ 1 → r1 then go to instruction I_a.	Increment contents of register #1
b1.	1-	If ≤ 0 THEN go to I_b else -1 → r1 and go to I_a.	Jump to instruction I_b if contents of register r1 is zero ELSE decrement contents of register #1