Efficient implementations of multicounter machines on oblivious turing machines, acyclic logic networks, and VLSI : (preprint)
Paul M. B. Vitanyi · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1981
A I-tape oblivious Turing machine can simulate a k-counter machine online in linear time and logarithmic space.This leads to a linear cost combinational logic network implementing n steps of a k-counter machine.In the VLSI model of computation we can simulate n steps of a k-counter machine in real-time on area O(k log n).A k-counter machine can be simulated in real-time by a (nonoblivious) machine without head reversals.Some results are•stated about oblivious k-counter languages.