Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape

Abstract

In this paper we consider the next more powerful restricted type of Turing machine, which cannot be handled by the existing lower bound arguments: Turing machines with one work tape and a two-way input tape. We show that one can simulate a deterministic Turing machine of this type with time bound $O(n^3 )$ by $\Sigma _2 $-Turing machine of the same type with time bound $O(n^2 \cdot \log ^2 n)$. This implies the new separation result $\Sigma _2 {\operatorname{TIME}}_1 (n) \nsubseteq {\operatorname{DTIME}}_1 ({{n^{{3 / 2}} } / {\log ^6 n}})$. Further, we improve Kannan’s separation result ${\operatorname{NTIME}}(n) \nsubseteq {\operatorname{DTIME}}_1 (n^{1.104} )$ to ${\operatorname{NTIME}}(n) \nsubseteq {\operatorname{DTIME}}_1 (n^{1.22} )$. Finally we show that with Turing machines of the considered type that use $2k$ alternations, the achieved speed-up increases and for large k approximates $t^{{1 / 2}} (n)$. In view of the close relationship between spacebounded Turing machines and time-bounded Turing machines with unboundedly many alternations, this refinement provides a link between our speed-up result and the well-known space-compression result for offline 1-tape Turing machines.