A counter machine or counter automaton is an
abstract machine used in a
formal logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
and
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
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.
Counter machines with three counters can compute any
partial recursive function of a single variable.
Counter machines with two counters are
Turing complete: they can simulate any appropriately-encoded Turing machine. Counter machines with only a single counter can recognize a proper superset of the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s and a subset of the
deterministic context free languages.
Basic features
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 (r
j, r
k): CoPY the contents of register ''r
j'' to register ''r
k'' leaving the contents of ''r
j'' intact.
* JZ (r, z): IF register ''r'' contains Zero THEN Jump to instruction ''z'' ELSE continue in sequence.
* JE (r
j, r
k, z): IF the contents of register ''r
j'' Equals the contents of register ''r
k'' 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).
Using the instructions mentioned above, various authors have discussed certain counter machines:
* set 1: , (Minsky (1961, 1967), Lambek (1961))
* set 2: , (Ershov (1958), Peter (1958) as interpreted by Shepherdson–Sturgis (1964); Minsky (1967); Schönhage (1980))
* set 3: , (Elgot–Robinson (1964), Minsky (1967))
The three counter machine base models have the same computational power since the instructions of one model can be derived from those of another. All are equivalent to the computational power of
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s. Due to their unary processing style, counter machines are typically exponentially slower than comparable Turing machines.
Alternative names, alternative models
The counter machine models go by a number of different names that may help to distinguish them by their peculiarities. In the following the instruction "JZDEC ( r )" is a compound instruction that tests to see if a register r is empty; if so then jump to instruction I
z, else if not then DECrement the contents of r:
* Minsky machine, because
Marvin Minsky (1961) formalized the model. Abacus machine, the name Lambek (1961) gave to his simplification of the Melzak (1961) model, and what Boolos–Burgess–Jeffrey (1974) call it. Lambek machine, an alternative name Boolos–Burgess–Jeffrey (1974) gave to the abacus machine. Usually uses instruction set (1), but instruction-execution is not default-sequential so the additional parameter 'z' appears to specify the next instruction after INC and as the alternative in JZDEC:
*:
* Program machine, program computer, the names Minsky (1967) gave the model because, like a
computer
A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
its instructions proceed sequentially unless a conditional jump is successful. Uses (usually) instruction set (1) but may be augmented similar to the Shepherson–Sturgis model. JZDEC is often split apart:
*:
* Successor machine, because it uses the 'successor operation' of, and closely resembles, the
Peano axioms. Used as a base for the successor RAM model. Uses instruction set (2) by e.g. Schönhage as a base for his RAM0 and RAM1 models that lead to his
pointer machine SMM model, also discussed briefly in van Emde Boas (1990):
*:
* Elgot–Robinson model, used to define their RASP model (1964). This model requires one empty register at the start (e.g.
0=0). (They augmented the same model with indirect addressing by use of an additional register to be used as an "index" register.)
*:
*Shepherdson–Sturgis machine, because these authors formally stated their model in an easily accessible exposition (1963). Uses instruction set (1) augmented with additional convenience instructions (JNZ is "Jump if Not Zero, used in place of JZ):
*:
* Other counter machines: Minsky (1967) demonstrates how to build the three base models (program/Minsky/Lambek-abacus, successor, and Elgot–Robinson) from the superset of available instructions described in the lead paragraph of this article. The Melzak (1961) model is quite different from the above because it includes 'add' and 'subtract' rather than 'increment' and 'decrement'. The proofs of Minsky (1961, 1967) that a single register will suffice for Turing equivalence requires the two instructions to encode and decode the
Gödel number in the register that represents the computation. Minsky shows that if two or more registers are available then the simpler INC, DEC etc. are adequate (but the
Gödel number is still required to demonstrate
Turing equivalence; also demonstrated in Elgot–Robinson 1964).
Formal definition
A counter machine consists of:
# Labeled unbounded integer-valued registers: a finite (or infinite in some models) set of registers ''r''
0 ... ''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
In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...
for more on this).
# 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
# List of labelled, sequential instructions: A finite list of instructions ''I''
0 ... ''I''
''m''. The program store (instructions of the
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
) is not in the same physical "space" as the registers. Usually, but not always, like
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...
s 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. Historically most models drew their instructions from this set:
::
: 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.''
Example: COPY the count from register #2 to #3
This example shows how to create three more useful instructions: ''clear'', ''unconditional jump'', and ''copy''.
* CLR ( j ): Clear the contents of register ''r
j'' to zero.
* J ( z ): Unconditionally jump to instruction ''I
z''.
* CPY ( s, d ): Copy the contents of source register ''r
s'' to destination register ''r
d''. (See
One-instruction set computer#Transport triggered architecture)
Afterward ''r
s'' will contain its original count (unlike MOVE which empties the source register, i.e., clears it to zero).
The basic set (1) is used as defined here:
Initial conditions
Initially, register #2 contains "2". Registers #0, #1 and #3 are empty (contain "0"). Register #0 remains unchanged throughout calculations because it is used for the unconditional jump. Register #1 is a scratch pad. The program begins with instruction 1.
Final conditions
The program HALTs with the contents of register #2 at its original count and the contents of register #3 equal to the original contents of register #2, i.e.,
:
=
Program high-level description
The program COPY ( #2, #3) has two parts. In the first part the program ''moves'' the contents of source register #2 to both scratch-pad #1 and to destination register #3; thus #1 and #3 will be ''copies'' of one another and of the original count in #2, but #2 is cleared in the process of decrementing it to zero. Unconditional jumps J (z) are done by tests of register #0, which always contains the number 0:
:
2→#3;
2→#1; 0 →#2
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:
:
1→#2; 0 →#1
Program
The program, highlighted in yellow, is shown written left-to-right in the upper right.
A "run" of the program is shown below. Time runs down the page. The instructions are in yellow, the registers in blue. The program is flipped 90 degrees, with the instruction numbers (addresses) along the top, the instruction mnemonics under the addresses, and the instruction parameters under the mnemonics (one per cell):
The partial recursive functions: building "convenience instructions" using recursion
The example above demonstrates how the first basic instructions can create three more instructions—unconditional jump J, CLR, CPY. In a sense CPY used both CLR and J plus the base set. If register #3 had had contents initially, the ''sum'' of contents of #2 and #3 would have ended up in #3. So to be fully accurate CPY program should have preceded its moves with CLR (1) and CLR (3).
However, we do see that ADD would have been possible, easily. And in fact the following is summary of how the
primitive recursive functions such as ADD, MULtiply and EXPonent can come about.
* Beginning instruction set:
* Define unconditional "Jump J (z)" in terms of JZ ( r0, z ) given that r0 contains 0.
:
* Define "CLeaR ( r ) in terms of the above:
:
* Define "CoPY ( r
j, r
k )" while preserving contents of r
j in terms of the above:
:
:: ''The above is the instruction set of Shepherdson–Sturgis (1963).''
* Define "ADD ( r
j, r
k, r
i )", (perhaps preserving the contents of r
j, and r
k ), by use of the above:
:
* Define " MULtiply ( r
j, r
k, r
i )" (MUL) (perhaps preserving the contents of r
j, r
k), in terms of the above:
:
* Define "EXPonential ( r
j, r
k, r
i )" (EXP) (perhaps preserving the contents of r
j, r
k ) in terms of the above,
:
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).
But what about full
Turing equivalence? We need to add the sixth operator—the
μ operator—to obtain the full equivalence, capable of creating the total- and partial-
recursive functions:
# Zero function (or constant function)
# Successor function
# Identity function
# Composition function
#
Primitive recursion (induction)
#
μ operator (unbounded search operator)
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 means that any mu recursive function can be implemented as a counter machine, despite the finite instruction set and program size of the counter machine design. However, the required construction may be counter-intuitive, even for functions that are relatively easy to define in more complex register machines such as the
random-access machine
In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...
. 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.
For instance, the above hierarchy of primitive recursive operators can be further extended past exponentiation into higher-ordered arrow operations in
Knuth's up-arrow notation. For any fixed
, the function
is primitive recursive, and can be implemented as a counter machine in a straightforward way. But the function
is not primitive recursive. One may be tempted to implement the up-arrow operator
using a construction similar to the successor, addition, multiplication, and exponentiation instructions above, by implementing a
call stack
In computer science, a call stack is a Stack (abstract data type), stack data structure that stores information about the active subroutines and block (programming), inline blocks of a computer program. This type of stack is also known as an exe ...
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.
Problems with the counter machine model
: ''The problems are discussed in detail in the article
Random-access machine
In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...
. The problems fall into two major classes and a third "inconvenience" class:''
(1) Unbounded ''capacities'' of registers versus bounded capacities of state-machine instructions: How will the machine create constants larger than the capacity of its finite-state machine?
(2) Unbounded ''numbers'' of registers versus bounded numbers of state-machine instructions: How will the machine access registers with address-numbers beyond the reach/capability of its finite-state machine?
(3) The fully reduced models are cumbersome:
Shepherdson and Sturgis (1963) are unapologetic about their 6-instruction set. They have made their choice based on "ease of programming... rather than economy" (p. 219 footnote 1).
Shepherdson and Sturgis' instructions (
indicates "contents of register r"):
** INCREMENT ( r ) ;
+1 → r
** DECREMENT ( r ) ;
-1 → r
** CLEAR ( r ) ; 0 → r
** COPY ( r
s to r
d ) ;
s">s→ r
d
** JUMP-UNCONDITIONAL to instruction I
z
** JUMP IF
=0 to instruction I
z
Minsky (1967) expanded his 2-instruction set to before his proof that a "Universal Program Machine" can be built with only two registers (p. 255ff).
Two-counter machines are Turing equivalent (with a caveat)
For every
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, there is a 2CM that simulates it, given that the 2CM's input and output are properly encoded. This is proved in Minsky's book (''Computation'', 1967, p. 255-258), and an alternative proof is sketched below in three steps. First, a Turing machine can be simulated by a finite-state machine (FSM) equipped with two stacks. Then, two stacks can be simulated by four counters. Finally, four counters can be simulated by two counters.
The two counters machine use the set of instruction .
Step 1: A Turing machine can be simulated by two stacks.
A Turing machine consists of an FSM and an infinite tape, initially filled with zeros, upon which the machine can write ones and zeros. At any time, the read/write head of the machine points to one cell on the tape. This tape can be conceptually cut in half at that point. Each half of the tape can be treated as a
stack, where the top is the cell nearest the read/write head, and the bottom is some distance away from the head, with all zeros on the tape beyond the bottom. Accordingly, a Turing machine can be simulated by an FSM plus two stacks. Moving the head left or right is equivalent to popping a bit from one stack and pushing it onto the other. Writing is equivalent to changing the bit before pushing it.
Step 2: A stack can be simulated by two counters.
A stack containing zeros and ones can be simulated by two counters when the bits on the stack are thought of as representing a
binary number
A binary number is a number expressed in the Radix, base-2 numeral system or binary numeral system, a method for representing numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A ''binary number'' may ...
(the topmost bit on the stack being the least significant bit). Pushing a zero onto the stack is equivalent to doubling the number. Pushing a one is equivalent to doubling and adding 1. Popping is equivalent to dividing by 2, where the
remainder
In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient ( integer division). In a ...
is the bit that was popped. Two counters can simulate this stack, in which one of the counters holds a number whose binary representation represents the bits on the stack, and the other counter is used as a scratchpad. To double the number in the first counter, the FSM can initialize the second counter to zero, then repeatedly decrement the first counter once and increment the second counter twice. This continues until the first counter reaches zero. At that point, the second counter will hold the doubled number. Halving is performed by decrementing one counter twice and increment the other once, and repeating until the first counter reaches zero. The remainder can be determined by whether it reached zero after an even or an
odd number of steps, where the parity of the number of steps is encoded in the state of the FSM.
Step 3: Four counters can be simulated by two counters.
As before, one of the counters is used as scratchpad. The other holds an
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
whose
prime factorization is 2
''a''3
''b''5
''c''7
''d''. The exponents ''a'', ''b'', ''c'', and ''d'' can be thought of as four virtual counters that are being packed (via
Gödel numbering) into a single real counter. If the real counter is set to zero then incremented once, that is equivalent to setting all the virtual counters to zero. If the real counter is doubled, that is equivalent to incrementing ''a'', and if it's halved, that's equivalent to decrementing ''a''. By a similar procedure, it can be multiplied or divided by 3, which is equivalent to incrementing or decrementing ''b''. Similarly, ''c'' and ''d'' can be incremented or decremented. To check if a virtual counter such as ''c'' is equal to zero, just divide the real counter by 5, see what the remainder is, then multiply by 5 and add back the remainder. That leaves the real counter unchanged. The remainder will have been nonzero if and only if ''c'' was zero.
As a result, an FSM with two counters can simulate four counters, which are in turn simulating two stacks, which are simulating a Turing machine. Therefore, an FSM plus two counters is at least as powerful as a Turing machine. A Turing machine can easily simulate an FSM with two counters, therefore the two machines have equivalent power.
The caveat: *If* its counters are initialised to ''N'' and 0, then a 2CM cannot calculate 2''N''
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 ''N''
2, sqrt(''N''), log
2(''N''), etc., appears in a paper by Schroeppel (1972). The result is not surprising, because the two-counter machine model was proved (by Minsky) to be universal only when the argument ''N'' is appropriately encoded (by Gödelization) to simulate a Turing machine whose initial tape contains ''N'' encoded in unary; moreover, the output of the two-counter machine will be similarly encoded. This phenomenon is typical of very small bases of computation whose universality is proved only by simulation (e.g., many
Turing tarpits, the smallest-known
universal Turing machines, etc.).
The proof is preceded by some interesting theorems:
* "Theorem: A three-counter machine can simulate a Turing machine" (p. 2, also cf Minsky 1967:170-174)
* "Theorem: A 3CM
hree-counter machinecan compute any partial recursive function of one variable. It starts with the argument
.e. ''N''in a counter, and (if it halts) leaves the answer
.e. F(''N'')in a counter." (p. 3)
* "Theorem: A counter machine can be simulated by a 2CM
wo-counter machine provided an obscure coding is accepted for the input and output"
W3X5Y7Z where the simulated counters are W, X, Y, Z">. 3; the "obscure coding" is: 2W3X5Y7Z where the simulated counters are W, X, Y, Z* "Theorem: Any counter machine can be simulated by a 2CM, provided an obscure coding is accepted for the input and output." (p. 3)
** "Corollary: the
halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
for 2CMs is unsolvable.
** "Corollary: A 2CM can compute any partial recursive function of one argument, provided the input is coded as 2
N and the output (if the machine halts) is coded as 2
answer." (p. 3)
* "Theorem: There is no two counter machine that calculates 2
''N'' f one counter is initialised to ''N''" (p. 11)
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). The main proof involves the notion that two-counter machines cannot compute arithmetic sequences with non-linear growth rates (p. 15) i.e. "the function 2
X grows more rapidly than any arithmetic progression." (p. 11).
A practical example of calculation by counting
The
Friden EC-130 calculator had no adder logic as such. Its logic was highly serial, doing arithmetic by counting. Internally, decimal digits were radix-1 — for instance, a six was represented by six consecutive pulses within the time slot allocated for that digit. Each time slot carried one digit, least significant first. 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.
Multiplication and division were done basically by repeated addition and subtraction. The square root version, the EC-132, effectively subtracted consecutive odd integers, each decrement requiring two consecutive subtractions. After the first, the minuend was incremented by one before the second subtraction.
See also
*
Pointer machine
*
Post–Turing machine
*
Random-access machine
In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...
*
Register machine
*
Wang B-machine
*
Vector addition system
References
Bibliography
* The original Boolos–Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 ''Abacus Computability''; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
* , reprinted in
*
*
*
* Develops
time hierarchy and
space hierarchy theorems for counter machines, analogous to the hierarchies for Turing machines.
*
* A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
*
*
* Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures.
* In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) ''Introduction to Metamathematics''.
* Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University.
*
* In particular see chapter 11: ''Models Similar to Digital Computers'' and chapter 14: ''Very Simple Bases for Computability''. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
* A valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems.
**
** English translation, Automat. Express 1 (1959), 20-23.
**
**
* Wherein Schönhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc.
* The author references Minsky 1967 and notes that "
Frances Yao independently proved the non-computability using a similar method in April 1971.
* Van Emde Boas' treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980—it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
* Presented at the meeting of the Association, June 23–25, 1954.
External links
* {{MathWorld, title=Register machine, urlname=RegisterMachine
Igblan - Minsky Register Machines
Register machines