About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SWAT 1967
Conference paper
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.