Accession Number : ADA018707

Title :   On Time Versus Space.

Descriptive Note : Technical rept.,

Corporate Author : CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hopcroft,John ; Paul,Wolfgang ; Valiant,Leslie

Report Date : DEC 1975

Pagination or Media Count : 19

Abstract : 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.

Descriptors :   *Computer programming, *Mathematical logic, Computations, Context sensitive grammars, Game theory, Theorems

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE