Counter Machine - Formal Definition

Formal Definition

A counter machine consists of:

1. Labeled unbounded integer-valued registers: a finite (or infinite in some models) set of registers r₀ ... r_n each of which can hold any single non-negative integer (0, 1, 2, ... - i.e. unbounded). The registers do their own arithmetic; there may or may not be one or more special registers e.g. "accumulator" (See Random access machine for more on this).
2. A state register that stores/identifies the current instruction to be executed. This register is finite and separate from the registers above; thus the counter machine model is an example of the Harvard architecture
3. List of labelled, sequential instructions: A finite list of instructions I₀ ... I_m. The program store (instructions of the finite state machine) is not in the same physical "space" as the registers. Usually, but not always, like computer programs the instructions are listed in sequential order; unless a jump is successful, the default sequence continues in numerical order. Each of the instructions in the list is from a (very) small set, but this set does not include indirection. The historically most models drew their instructions from this set:

{ Increment (r), Decrement (r), Clear (r); Copy (r_j,r_k), conditional Jump if contents of r=0, conditional Jump if r_j=r_k, unconditional Jump, HALT }

Some models have either further atomized some of the above into no-parameter instructions, or combined them into a single instruction such as "Decrement" preceded by conditional jump-if-zero "JZ ( r, z )" . The atomization of instructions or the inclusion of convenience instructions causes no change in conceptual power, as any program in one variant can be straightforwardly translated to the other.

Alternative instruction-sets are discussed in the supplement Register machine models.