On Time Versus Space.
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
It is shown that every deterministic multitape Turing machine of time complexity tn can be simulated by a deterministic Turing machine of tape complexity tnlog tn. Consequently for tape constructable tn, the class of languages recognizable by multitape Turing machines of time complexity tn is strictly contained in the class of languages recognized by Turing machines of tape complexity tn. In particular the context sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines.
- Computer Programming and Software