On Time Versus Space
- 1 April 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 24 (2), 332-337
- https://doi.org/10.1145/322003.322015
Abstract
It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity t(n) is strictly contained in the class of languages recognized by Turing machines of tape complexity t(n). In particular, the context sensitive languages can not be recognized in linear time by deterministic multitape Turing machines. Keywords and phrases: Turing machines, time complexity, tape complexity.Keywords
This publication has 7 references indexed in Scilit:
- An observation on time-storage trade offPublished by Association for Computing Machinery (ACM) ,1973
- Tape bounds for time-bounded turing machinesJournal of Computer and System Sciences, 1972
- Some Results on Tape-Bounded Turing MachinesJournal of the ACM, 1969
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966
- On-Line Turing Machine ComputationsIEEE Transactions on Electronic Computers, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965