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:
- Deterministic or non-deterministic FSM plus two counters
- Non-deterministic FSM plus one stack
- Non-deterministic FSM plus one counter
- Deterministic FSM plus one counter
- 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 computer takes up where psychoanalysis left off. It takes the ideas of a decentered self and makes it more concrete by modeling mind as a multiprocessing machine.”
—Sherry Turkle (b. 1948)
“Already nature is serving all those uses which science slowly derives on a much higher and grander scale to him that will be served by her. When the sunshine falls on the path of the poet, he enjoys all those pure benefits and pleasures which the arts slowly and partially realize from age to age. The winds which fan his cheek waft him the sum of that profit and happiness which their lagging inventions supply.”
—Henry David Thoreau (1817–1862)