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.

Read more about this topic:  Counter

Famous quotes containing the words computer and/or science:

    “The analogy between the mind and a computer fails for many reasons. The brain is constructed by principles that assure diversity and degeneracy. Unlike a computer, it has no replicative memory. It is historical and value driven. It forms categories by internal criteria and by constraints acting at many scales, not by means of a syntactically constructed program. The world with which the brain interacts is not unequivocally made up of classical categories.”
    —Gerald M. Edelman (b. 1928)

    ““You are bothered, I suppose, by the idea that you can’t possibly believe in miracles and mysteries, and therefore can’t make a good wife for Hazard. You might just as well make yourself unhappy by doubting whether you would make a good wife to me because you can’t believe the first axiom in Euclid. There is no science which does not begin by requiring you to believe the incredible.””
    —Henry Brooks Adams (1838–1918)