Skip to main content


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

Please use this identifier to cite or link to this item:
Title: Tape Reversal Bounded Turing Machine Computations
Authors: Hartmanis, Juris
Keywords: computer science
technical report
Issue Date: Feb-1968
Publisher: Cornell University
Abstract: This paper studies the classification of recursive sets by the number of tape reversals required for their recognition on a two-tape Turing machine with a one-way input tape. This measure yields a rich hierarchy of tape reversal limited complexity classes and their properties and ordering are investigated. The most striking difference between this and the previously studied complexity measures lies in the fact that the "speed-up" theorem does not hold for slowly growing tape reversal complexity classes. These differences are discussed, and several relations between the different complexity measures and languages are established.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
68-7.pdf941.67 kBAdobe PDFView/Open
68-7.ps353.53 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us