# Counter machine reference model

﻿
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.

## 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).

## 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

## 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 strategy 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.

### 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)
1. JZ (rX,i1)
2. JZ (r0,i2)
IF rX=0 THEN i1 ELSE i2
DECJZ(r,i)
1. JZ (r,*i)
2. DEC(r)
Test r=0; if r = 0 then DEC
INCJ(r,i)
1. INC(r)
2. J (i)
INC and J.
CLR(r)
1. JZ (r,*+3)
2. DEC(r)
3. 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)
1. CLR (r)
2. ( 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.

### 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 instructions".

See Talk page.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Counter machine — A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded… …   Wikipedia

• Counter machine models — 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 species the counter machine of the genus… …   Wikipedia

• Machine pistol — This article is about full auto or burst capable pistols. For semi automatic weapons, see semi automatic pistol. A fully automatic Steyr M1912, which was used as a side arm by the Austro Hungarian Army A machine pistol is a handgun style,… …   Wikipedia

• Model checking — This article is about checking of models in computer science. For the checking of models in statistics, see regression model validation. In computer science, model checking refers to the following problem: Given a model of a system, test… …   Wikipedia

• Machine Robo Mugenbine — The current logo of the Machine Robo Mugenbine toyline. Machine Robo Mugenbine (マシンロボムゲンバイン?), also called Multiple General Node Combine System …   Wikipedia

• Register machine — In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Contents 1 Overview 2 Formal definition 3 …   Wikipedia

• Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… …   Wikipedia

• Pointer machine — In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine.Depending on the type, a pointer machine may be called a linking automaton, a KU machine, an SMM, an… …   Wikipedia

• Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

• Beechcraft Model 18 — Model 18 Instructor and pilot in a Beechcraft AT 7 doing navigation training at Kelly Field, TX. Role Trainer …   Wikipedia