Real-Time Simulation of Multihead Tape Units
Patrick C. Fischer, Albert R. Meyer, Arnold L. Rosenberg · Journal of the ACM · 1972
The main result of this paper is that, given a Turing machine with several readwrite 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.