Counter - Computer Science Counters

Computer Science Counters

In computability theory, a counter is considered a type of memory. A counter stores a single natural number (initially zero) and can be arbitrarily many digits long. A counter is usually considered in conjunction with a finite-state machine (FSM), which can perform the following operations on the counter:

• Check whether the counter is zero
• Increment the counter by one.
• Decrement the counter by one (if it's already zero, this leaves it unchanged).

The following machines are listed in order of power, with each one being strictly more powerful than the one below it:

1. Deterministic or non-deterministic FSM plus two counters
2. Non-deterministic FSM plus one stack
3. Non-deterministic FSM plus one counter
4. Deterministic FSM plus one counter
5. Deterministic or non-deterministic FSM.

For the first and last, it doesn't matter whether the FSM is a deterministic finite automaton or a nondeterministic finite automaton. They have power. The first two and the last one are levels of the Chomsky hierarchy.

The first machine, an FSM plus two counters, is equivalent in power to a Turing machine. See the article on counter machines for a proof.