1982-07-12
Efficient simulations of multicounter machines
Publication
Publication
Presented at the
European Conference on Numerical Mathematics and Advanced Applications (July 1982), Aarhus, Denmark
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.
Additional Metadata | |
---|---|
doi.org/10.1007/BFb0012799 | |
European Conference on Numerical Mathematics and Advanced Applications | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), 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
|