Note on tape reversal complexity of languages

The number of tape reversals required for the recognition of a set of inputs by a 1-tape Turing machine (TM) has been proposed before as a measure of complexiIt is shown that if a set is recognizable by a multi-tape TM with no more than R(n) tape reversals, where n is the input length, then the set is recogIt is also shown that if a set is recognizable by a multi-tape TM within time T(n), then the set is recognizable by a 1-tape off-line TM with no more thanUpper bounds on the number of reversals necessary for the recognition of a number of well-known classes of languages are also obtained