Turing machines with several read-write heads preliminary report

Abstract

Turing machines with more than one work tape or more than one read-write head per tape have been considered by several investigators studying time limited computations ([3],[4], [8]). Primary emphasis has been on multitape machines - with exactly one head per tape - since these machines naturally model the familiar situation in which a single computer controls several tape drives. To the authors' knowledge, a tape unit which provided for independent movement by several heads on the same tape has never been produced, possr because of the problems in designing a take-up reel for tape between a pair of heads. One implication of the main theorem of this preliminary report is that a multihead tape unit theoretically need never be constructed. Stated informally, we prove: Any program written to utilize multihead tape units for internal storage can effectively be rewritten to run at precisely the same speed on a machine wlth several tapes but only one head per tape.