Counting is Easy

Details Counting is Easy Counting is Easy

2001-10-18

arxiv.org/abs/cs/0110038v1

J. Seiferas and P.M.B. Vitanyi, Counting is easy, J. Assoc. Comp. Mach. 35 (1988), pp. 985-1000

Computer Science

Computational Complexity

Scientific paper

For any fixed $k$, a remarkably simple single-tape Turing machine can simulate $k$ independent counters in real time. Informally, a counter is a storage unit that maintains a single integer (initially 0), incrementing it, decrementing it, or reporting its sign (positive, negative, or zero) on command. Any automaton that responds to each successive command as a counter would is said to simulate a counter. (Only for a sign inquiry is the response of interest, of course. And zeroness is the only real issue, since a simulator can readily use zero detection to keep track of positivity and negativity in finite-state control. In this paper we describe a remarkably simple real-time simulation, based on just five simple rewriting rules, of any fixed number $k$ of independent counters. On a Turing machine with a single, binary work tape, the simulation runs in real time, handling an arbitrary counter command at each step. The space used by the simulation can be held to $(k+\epsilon) \log_2 n$ bits for the first $n$ commands, for any specified $\epsilon > 0$.

Affiliated with

Also associated with

No associations

Rating

Counting is Easy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting is Easy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting is Easy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-283587