Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Computational Complexity of One-Tape Turing Machine Computations

Computational Complexity of One-Tape Turing Machine Computations

File(s)
68-3.pdf (1.93 MB)
68-3.ps (976.18 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5880
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
Abstract

This paper is concerned with the quantitative aspects of one-tape Turing machine computations. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of non-regular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a non-regular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.

Date Issued
1968-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR68-3
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance