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
|
|
