
doi: 10.1137/0214001
A k-counter machine consists of a finite control connected to an input and an output terminal, and k counters each capable of containing any integer. At the start of a computation the finite control is in initial state, and all counters are set to zero. A step of computation is determined by the state of the finite control, by the symbol scanned at the input terminal and by the set of counters which contain zero, and consists of independently altering the contents of each counter by -1, 0, \(+1\), changing the state of the finite control and producing an output string (possibly empty). A one-tape Turing machine consists of a finite control connected to an input and output terminal, and a single head storage tape. A Turing machine is oblivious if the movements of the storage tape head is a fixed function independent of the particular input to the machine. The main result of the paper is: Each multicounter machine can be simulated by an oblivious one-tape Turing machine in real time, using logarithmic space.
real-time simulation, finite control, multicounter machine, Models of computation (Turing machines, etc.), oblivious one-tape Turing machine
real-time simulation, finite control, multicounter machine, Models of computation (Turing machines, etc.), oblivious one-tape Turing machine
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
