Accession Number:

ADA018707

Title:

On Time Versus Space.

Descriptive Note:

Technical rept.,

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Report Date:

1975-12-01

Pagination or Media Count:

19.0

Abstract:

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE