Abstract | ||
---|---|---|
The main result of this paper is that, given a Turing machine with several read- write heads per tape, one can effectively construct an equivalent multitape Turing machine with a single read-write head per tape, which runs at precisely the same speed. This result implies that serial storage may be used to handle files requiring several points of immediate two-way read-write access without interruptions for rewinds, etc. It also yields simplified proofs of several results in the literature of computational complexity. |
Year | DOI | Venue |
---|---|---|
1972 | 10.1145/321724.321726 | J. ACM |
Keywords | DocType | Volume |
buffer,multihead tape units,Real-Time Simulation,multitape turing machine,real-time computation,simulation,computational complexity,Multihead Tape Units | Journal | 19 |
Issue | ISSN | Citations |
4 | 0004-5411 | 42 |
PageRank | References | Authors |
26.13 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Patrick C. Fischer | 1 | 42 | 26.13 |
Albert R. Meyer | 2 | 1729 | 604.47 |
Arnold L. Rosenberg | 3 | 2107 | 640.21 |