On the Relationship Between Deterministic Time and Deterministic Reversal

We investigate the relationship between the time and the reversal complexity measure for deterministic Turing machines. It is shown that for any function T DT IME(T ) ` DREVERSAL( p T ): Keywords: Computational complexity, Turing machine, reversal, time complexity 1 Introduction Besides time and space, the number of reversals made by the tape heads during a computation is an important and widely used complexity measure for Turing machines (TM). The reversal complexity was introduced by Hartmanis ([5]) and Fischer ([4]) and intensively studied by many authors. For example, it has been shown that the reversal complexity on multitape deterministic TMs is intimately connected with parallel time ([3],[6],[8]). In this paper we investigate the relationship between reversals and deterministic time. It is obvious that the heads of a multitape deterministic TM (DTM) working in time T (n) make at most O(T (n)) reversals. Moreover, it is easy to see that a multitape DTM of time complexity T (n..