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.
The counter machine models go by a number of different names that may help to distinguish them by their peculiarities.
Afterward rs will contain its original count (unlike MOVE which empties the source register, i.e., clears it to zero).
Unconditional jumps J (z) are done by tests of register #0, which always contains the number 0: In the second the part the program moves (returns, restores) the contents of scratch-pad #1 back to #2, clearing the scratch-pad #1 in the process: The program, highlighted in yellow, is shown written left-to-right in the upper right.
And in fact the following is summary of how the primitive recursive functions such as ADD, MULtiply and EXPonent can come about.
[2] In general, we can build any partial- or total- primitive recursive function that we wish, by using the same methods.
Indeed, Minsky (1967), Shepherdson–Sturgis (1963) and Boolos–Burgess–Jeffrey (1974) give demonstrations of how to form the five primitive recursive function "operators" (1-5 below) from the base set (1).
We need to add the sixth operator—the μ operator—to obtain the full equivalence, capable of creating the total- and partial- recursive functions: The authors show that this is done easily within any of the available base sets (1, 2, or 3) (an example can be found at μ operator).
This is because the μ operator can iterate an unbounded number of times, but any given counter machine cannot address an unbounded number of distinct registers due to the finite size of its instruction list.
using a construction similar to the successor, addition, multiplication, and exponentiation instructions above, by implementing a call stack so that the function can be applied recursively on smaller values of
This idea is similar to how one may implement the function in practice in many programming languages.
However, the counter machine cannot use an unbounded number of registers in its computation, which would be necessary to implement a call stack that can grow arbitrarily large.
The up-arrow operation can still be implemented as a counter machine since it is mu recursive, however the function would be implemented by encoding an unbounded amount of information inside a finite number of registers, such as by using Gödel numbering.
(3) The fully reduced models are cumbersome: Shepherdson and Sturgis (1963) are unapologetic about their 6-instruction set.
This is proved in Minsky's book (Computation, 1967, p. 255-258), and an alternative proof is sketched below in three steps.
The two counters machine use the set of instruction { INC ( r, z ), JZDEC ( r, ztrue, zfalse) }.
Moving the head left or right is equivalent to popping a bit from one stack and pushing it onto the other.
By a similar procedure, it can be multiplied or divided by 3, which is equivalent to incrementing or decrementing b.
This result, together with a list of other functions of N that are not calculable by a two-counter machine — when initialised with N in one counter and 0 in the other — such as N2, sqrt(N), log2(N), etc., appears in a paper by Schroeppel (1972).
The proof is preceded by some interesting theorems: With regard to the second theorem that "A 3CM can compute any partial recursive function" the author challenges the reader with a "Hard Problem: Multiply two numbers using only three counters" (p. 2).
Carries set a flip-flop which caused one count to be added to the digit in the next time slot.
Adding was done by an up-counter, while subtracting was done by a down-counter, with a similar scheme for dealing with borrows.
The time slot scheme defined six registers of 13 decimal digits, each with a sign bit.