Counting is Easy
| dc.creator | Seiferas, Joel | |
| dc.creator | Vitanyi, Paul | |
| dc.date | 2001-10-18 | |
| dc.date.accessioned | 2026-07-07T03:17:49Z | |
| dc.date.available | 2026-07-07T03:17:49Z | |
| dc.description | 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+ε) \log_2 n$ bits for the first $n$ commands, for any specified $ε> 0$. | |
| dc.identifier | https://arxiv.org/abs/cs/0110038 | |
| dc.identifier | http://arxiv.org/abs/cs/0110038 | |
| dc.identifier | J. Seiferas and P.M.B. Vitanyi, Counting is easy, J. Assoc. Comp. Mach. 35 (1988), pp. 985-1000 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30864 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | E.1, F.1.1., F.2.2, G.2.1, E.2, E.4 | |
| dc.title | Counting is Easy | |
| dc.type | text |