# Combinatorial lower bound arguments for deterministic and
nondeterministic Turing machines

### Abstract:

We introduce new techniques for proving quadratic lower bounds for
deterministic and nondeterminisitc 1-tape Turing machines (all considered
Turing machines have an additional one-way input tape). In particular, we
derive for the simulation of 2-tape Turing machines by 1-tape Turing
machines an optimal quadratic lower bound in the deterministic case and a
nearly optimal lower bound in the nonderterministic case. This answers the
rather old question whether the computing power of the considered types of
Turing machines is significantly increased when more than one tape is used
(problem Nos. 1 and 7 in the list of Duris, Galil, Paul, Reischuk
[3]). Further, we demonstrate a substantial superiority of nonderterminism
over determinism and of co-nondeterminism over nondeterminism for 1-tage
Turing machines

**Reference:** W. Maass.
Combinatorial lower bound arguments for deterministic and nondeterministic
Turing machines.
*Transactions of the American Mathematical Society*, 292(2):675-693,
1985.
hard copy.