Limited random access turing machines
- 1 October 1968
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 356-367
- https://doi.org/10.1109/swat.1968.15
Abstract
The model of an online multitape Turing machine is generalized by adding a bounded number of repositioning operations to the shift repertoire. It is proved that any such limited random access Turing machine can be effectively replaced by an equivalent conventional Turing machine which operates in the same time. This result yields simplified proofs and extensions of several results in the literature.Keywords
This publication has 6 references indexed in Scilit:
- Counter machines and counter languagesTheory of Computing Systems, 1968
- Real-Time Definable LanguagesJournal of the ACM, 1967
- Turing machines with a schedule to keepInformation and Control, 1967
- Turing machines with several read-write headsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1967
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Real time computationIsrael Journal of Mathematics, 1963