Efficient Implementations of Multicounter Machines for Oblivious Turing Machines, Acyclic Logic Networks, and VLSI

摘要

The dependence of the required time and storage, to maintain counts, on storage structure and organization as well as the cost required by a combinatorial network are investigated. Results show that a one-tape oblivious Turing machine can simulate a k-counter machine on-line 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 it is possible to simulate n steps of a k-counter machine in real time on area Omicron (k log n). A k-counter machine can be simulated in real time by a nonoblivious machine without head reversals. Results are also stated for oblivious k-counter languages.