Real-Time Simulation of Multihead Tape Units

Abstract

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. © 1972, ACM. All rights reserved.