Portal de Periódicos da CAPES

An optimal lower bound for turing machines with one work tape and a two-way input tape

1986; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-16486-3_103

1611-3349

Wolfgang Maaß, Georg Schnitger,

semigroups and automata theory

This paper contains the first concrete lower bound argument for Turing machines with one work tape and a two-way input tape (these Turing machines are often called "offline 1-tape Turing machines"). In particular we prove an optimal lower bound of Ω(n3/2/(log n)1/2) for transposing a matrix with elements of bit length ∘(logn) (where n is the length of the total input). This implies a lower bound of Ω(n3/2/(log n)1/2) for sorting on the considered type of Turing machine. We also get as corollaries the first nonlinear lower bound for the most difficult version of the two tapes — versus — one problem, and a separation of the considered type of Turing machine from that with an additional write-only output tape.