# Quadratic lower bounds for deterministic and nondeterministic one-tape
Turing machines

### Abstract:

We introduce new techniques for proving quadratic lower bounds for
deterministic and nondeterministic i-tape Turing machines (all considered
Turing machines have an additional oneway input tape). In particular we
produce quadratic lower bounds for the simulation of 2-tape TM's by l-tape
TM's and thus answer a rather old question (problem No.1 and No.7 in the l i
s t of Duris, Galil, Paul, Reischuk [3]). Further we demo6strate a
substantial superiority of nondeterminism over determinism and of
co-nondeterminism over nondeterminism for l-tape TM's.

**Reference:** W. Maass.
Quadratic lower bounds for deterministic and nondeterministic one-tape
Turing machines.
In *Proceedings of 16th Annual ACM Symp. on Theory of Computing*, pages
401-408, 1984.