Efficient simulations of multicounter machines
An oblivious 1-tape Turing machine can on-line simulate a multicounter machine in linear time and logarithmic space. This leads to a linear cost combinational logic network implementing the first n steps of a multicounter machine and also to a linear time/logarithmic space on-line simulation by an oblivious logarithmic cost RAM. An oblivious log* n-head tape unit can simulate the first n steps of a multicounter machine in real-time, which leads to a linear cost combinational logic network with a constant data rate.
|European Conference on Numerical Mathematics and Advanced Applications|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam, The Netherlands|
Vitányi, P.M.B. (1982). Efficient simulations of multicounter machines. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 546–560). doi:10.1007/BFb0012799