Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/5880
Title: Computational Complexity of One-Tape Turing Machine Computations
Authors: Hartmanis, Juris
Keywords: computer science
technical report
Issue Date: Jan-1968
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR68-3
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.
URI: http://hdl.handle.net/1813/5880
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
68-3.pdf1.97 MBAdobe PDFView/Open
68-3.ps976.18 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us