Show simple item record

dc.contributor.authorHartmanis, Jurisen_US
dc.date.accessioned2007-04-09T21:02:44Z
dc.date.available2007-04-09T21:02:44Z
dc.date.issued1968-02en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR68-7en_US
dc.identifier.urihttps://hdl.handle.net/1813/5884
dc.description.abstractThis 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.en_US
dc.format.extent964265 bytes
dc.format.extent362017 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleTape Reversal Bounded Turing Machine Computationsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics