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 r0 ... rn 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 I0 ... Im. 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 (rj,rk), conditional Jump if contents of r=0, conditional Jump if rj=rk, 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.

Read more about this topic:  Counter Machine

Other articles related to "formal definition":

Big O Notation - Example
... In typical usage, the formal definition of O notation is not used directly rather, the O notation for a function f(x) is derived by the following simplification rules If f(x) is a sum of several terms ... One may confirm this calculation using the formal definition let f(x) = 6x4 − 2x3 + 5 and g(x) = x4 ... Applying the formal definition from above, the statement that f(x) = O(x4) is equivalent to its expansion, for some suitable choice of x0 and M and for all ...
Atomic SP-DEVS - Formal Definition
... The above controller for crosswalk lights can be modeled by an atomic SP-DEVS model ... Formally, an atomic SP-DEVS is a 7-tuple where is a finite set of input events is a finite set of output events is a finite set of states is the initial state is the time advanced function which defines the lifespan of a state where is the set of non-negative rational numbers plus infinity ...

Famous quotes containing the words definition and/or formal:

    Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.
    Willard Van Orman Quine (b. 1908)

    The manifestation of poetry in external life is formal perfection. True sentiment grows within, and art must represent internal phenomena externally.
    Franz Grillparzer (1791–1872)