Tape-reversal bounded turing machine com
โ
J. Hartmanis
๐
Article
๐
1968
๐
Elsevier Science
๐
English
โ 667 KB
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 inves