John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
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.
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Joseph Y. Halpern
aaai 1996
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.