Counter-machine model
This page supplements counter machine.
Although some authors use the name "register machine" synonymously with "counter machine", this article will give details and examples of only of the most primitive speciesthe "counter machine"of the genus "register machine."
Within the species "counter machine" there are a number of varieties: the models of Hermes, Kaphengst, Ershov, Péter, Minsky and Minsky, Melzak, Lambek, Shepherdson and Sturgis, and Schönhage. These models will be described in more detail in the following.
The models in more detail
1954: Hermes' model
Shepherdson and Sturgis 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".Shepherdson and Sturgis observe that:
The only two arithmetic instructions are
- Successor operation
- Testing two numbers for equality
Kaphengst's paper is written in German; Sheperdson and Sturgis's 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's 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 |
Shepherdson and Sturgis 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 Minsky ; see more in the section below.
| Action: | Description: | ||
| a: | P | + 1 → A | Increment contents of accumulator A |
| d. | C | → rk, → rj | Copy contents of register rj to register rk |
| 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 rj = contents of rk, else "set" E=1 |
1958: Ershov's class of operator algorithms
Shepherdson and Sturgis 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 | → rk, → rj | Copy contents of register rj to register rk |
| d'. | C' | +1 → rk, → rj | Copy incremented contents of register rj to register rk |
| 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 rj is less than or equal to contents of rk, else jump to E=2 |
1958: Péter's "treatment"
Shepherdson and Sturgis 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 Ij1. | Increment contents of register r and go to instruction Ij1. |
| b. | If ≤ 0 THEN go to instr. Ij2 ELSE -1 → r and go to instr. Ij1 | IF contents of register r equals zero THEN jump to instruction Ij2; ELSE decrement contents of register r and jump to instr. Ij1. |
The first theorem is the context of a second "Theorem IIa" that
| Action: | Description: | ||
| a. | MULT | *Kj → r1; go to instruction Ij1. | Multiply contents of register r1 by constant Kj |
| b. | /Kj = 0 then go to instruction Ij2 else go to Ij1. | If division of contents of register 1 by constant Kj has no remainder then instr. Ij1 else instr. Ij2 |
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 phrases indefinitely large number of locations and finite number of counters here are important. This model is different than the Minsky model that allows for a finite number of locations with unbounded capacity for "markers".
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 Boolos-Burgess-Jeffrey.
| Action: | Description: | ||
| a. | X+ | + 1 → r; go to instruction Ia. | Increment contents of register r |
| b. | X- | If ≤ 0, go to instr.Ib else -1 → r and go to instr. Ia | First test for zero, then decrement contents of register r |
Abacus model of Boolos-Burgess, 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 Ia 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 Ia. | Increment contents of register #1 |
| b1. | 1- | If ≤ 0 THEN go to Ib else -1 → r1 and go to Ia. | Jump to instruction Ib if contents of register r1 is zero ELSE decrement contents of register #1 |
1963: Shepherdson and Sturgis's model
On page 218 Shepherdson and Sturgis references Minsky as it appeared for them in the form of an MIT Lincoln Laboratory report:Their model is strongly influenced by the model and the spirit of Hao Wang and his Wang B-machine. They "sum up by saying":
Unlimited Register Machine URM: This, their "most flexible machine... consists of a denumerable sequence of registers numbered 1, 2, 3,..., each of which can store any natural number...Each particular program, however involves only a finite number of these registers". In other words, the number of registers is potentially infinite, and each register's "size" is infinite.
They offer the following instruction set, and the following "Notes":
| URM model: | Action: | Description: | |
| a. | P | + 1 → r | Increment contents of register r |
| b. | D | - 1 → r | Decrement contents of register r |
| c: | O | 0 → r | Zero register r |
| d. | C | → rk, → rj, | Copy contents of register rj to register rk |
| e. | J | Jump to "Exit 1" | Unconditional jump to "Exit #1" |
| f: | J | IF = 0 THEN jump to "Exit 1" ELSE next instruction | IF contents of register r = 0 then jump to instruction "Exit 1" else next instruction |
Notes.
- This set of instructions is chosen for ease of programming the computation of partial recursive functions rather than economy; it is shown in Section 4 that this set is equivalent to a smaller set.
- There are infinitely many instructions in this list since m, n range over all positive integers.
- In instructions a, b, c, d the contents of all registers except n are supposed to be left unchanged; in instructions e, f, the contents of all registers are unchanged.
| Reduced URM: | Action: | Description: | |
| a1. | P | + 1 → r | Increment contents of register r |
| b1. | D | - 1 → r | Decrement contents of register r |
| ~f1: | J | IF ≠ 0 THEN jump to "Exit 1" | If contents of register m ≠ 0 THEN jump to instruction "Exit 1" ELSE continue |
Limited Register Machine LRM: Here they restrict the machine to a finite number of registers N, but they also allow more registers to "be brought in" or removed if empty. They show that the remove-register instruction need not require an empty register.
Single-Register Machine SRM: Here they are implementing the tag system of Emil Post and thereby allow only writing to the end of the string and erasing from the beginning. This is shown in their Figure 1 as a tape with a read head on the left and a write head on the right, and it can only move the tape right. "A" is their "word" :
They also provide a model as "a stack of cards" with the symbols :
- add card at top printed 1
- add card at top printed 1
- remove bottom card; if printed 1 jump to instruction m, else next instruction.
1967: Minsky's "Simple Universal Base for a Program Computer"
The following are definitions of the various instructions he treats:
| Action: | Description: | ||
| a. | 0 → r | Zero register r | |
| b. | + 1 → r | Increment contents of register r | |
| c. | IF = 0 THEN jump to instruction z ELSE next instruction | Test register r and jump to instruction z if contents is zero; if not, decrement contents of register r | |
| d. | If ≠ 0 THEN -1 → r ELSE next instruction | IF contents of register r not zero decrement contents of register r and jump to zth instruction, else if 0 then next instruction | |
| e. | → rk, → rj | Copy contents of register rj to register rk | |
| f. | RPT a:. Repeat cannot operate within its own range. | Do until contents of register = 0: Repeat instructions m thru n. When = 0, go to next instruction. | |
| g. | HALT | ||
| h. | goto | Jump to instruction z | Unconditional jump to instruction z |
| i. | If ≠ THEN jump to zth instruction ELSE next instruction | Conditional jump: if contents of register rj not equal to contents of register rk THEN jump to instruction z ELSE next instruction | |
| j. | * | RPT a:. Repeat can operate within its own range. | * Note: RPT must be in an infinite register |
Minsky begins with a model that consists of the three operations plus HALT:
He observes that we can dispense with if we allow for a specific register e.g. w already "empty". Later he compresses the three, into two.
But he admits the model is easier if he adds some -instructions and "go". He builds "go" out of the register w pre-set to 0, so that is an unconditional jump.
In his section 11.5 "The equivalence of Program Machines with General-recursive functions" he introduces two new subroutines:
He proceeds to show how to replace the "successor-predecessor" set with the "successor-equality" set. And then he defines his "REPEAT" and shows that we can define any primitive recursive function by the "successor-repeat" set ):
1980: Schönhage's 0-parameter model RAM0
Schönhage developed his computational model in context of a "new" model he called the Storage Machine Modification model, his variety of pointer machine. His development described a RAM model with a remarkable instruction set requiring no operands at all, excepting, perhaps, the "conditional jump" :The way Schönhage did this is of interest. He atomizes the conventional register "address:datum" into its two parts: "address", and "datum", and generates the "address" in a specific register n to which the finite-state machine instructions would have access, and provides an "accumulator" register z where all arithmetic operations are to occur.
In his particular RAM0 model has only two "arithmetic operations""Z" for "set contents of register z to zero", and "A" for "add one to contents of register z". The only access to address-register n is via a copy-from-A-to-N instruction called "set address n". To store a "datum" in accumulator z in a given register, the machine uses the contents of n to specify the register's address and register z to supply the datum to be sent to the register.
Peculiarities: A first peculiarity of the Schönhage RAM0 is how it "loads" something into register z: register z first supplies the register-address and then secondly, receives the datum from the registera form of indirect "load". The second peculiarity is the specification of the COMPARE operation. This is a "jump if accumulator-register z=zero. Apparently if the test fails the machine skips over the next instruction which always must be in the form of "goto λ" where "λ" is the jump-to address. The instruction"compare contents of z to zero" is unlike the Schonhage successor-RAM1 model with the more conventional "compare contents of register z to contents of register a for equality".
Primarily for referencethis is a RAM model, not a counter-machine modelthe following is the Schönhage RAM0 instruction set:
| Instruction | Action: | Description: | |
| 1 | Z | 0 → z | Clear accumulator-register z |
| 2 | A | + 1 → z | Increment the contents of accumulator-register z |
| 3 | N | → n, → z | "Set address n": copy contents of accumulator z into address-register n |
| 4 | L | ] → z | Indirectly copy into accumulator z the contents of the register pointed to by accumulator z |
| 5 | S | → | Indirectly store the contents of accumulator z into the register pointed to by the contents of address-register n |
| 6 | C | If = 0 skip the next instruction | If contents of accumulator z = 0 THEN skip next instruction else continue |
| 7 | goto Iλ | Unconditional goto instruction Iλ | Unconditional goto instruction Iλ |
Again, the above instruction set is for a random-access machine, a RAMa counter machine with indirect addressing; instruction "N" allows for indirect storage of the accumulator, and instruction "L" allows for indirect load of the accumulator.
While peculiar, Schönhage's model shows how the conventional counter-machine's "register-to-register" or "read-modify-write" instruction set can be atomized to its simplest 0-parameter form.