On Time Versus Space
John E. Hopcroft, Wolfgang J. Paul, Leslie Gabriel Valiant · Journal of the ACM · 1977
It is shown that every deterministic multitape Turing machine of time complexity t ( n ) can be simulated by a deterministic Turing machine of tape 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 cannot be recognized in linear time by deterministic multitape Turing machines.