Machine à compteurs

A counter machine is an abstract machine used in a 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 registers, each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorithms may be designed in such a matter to avoid interlocking, the simultaneous writing operation by two (or more) threads to the same memory address. For a given counter machine model the instruction set is tiny—from just one to six or seven instructions. Most models contain a few arithmetic operations and at least one conditional operation (if condition is true, then jump). Three base models, each using three instructions, are drawn from the following collection. (The abbreviations are arbitrary.) CLR (r): CLeaR register r. (Set r to zero.) INC (r): INCrement the contents of register r. DEC (r): DECrement the contents of register r. CPY (rj, rk): CoPY the contents of register rj to register rk leaving the contents of rj intact. JZ (r, z): IF register r contains Zero THEN Jump to instruction z ELSE continue in sequence. JE (rj, rk, z): IF the contents of register rj Equals the contents of register rk THEN Jump to instruction z ELSE continue in sequence. In addition, a machine usually has a HALT instruction, which stops the machine (normally after the result has been computed).