Additional Exercise 1
Show that any language accepted by a nondeterministic k-tape Turing
machine in f(n) time can be accepted by a nondeterministic 2-tape
Turing machine in f(n) time (in contrast to deterministic Turing
machines, where such a reduction in the number of tapes appears to
cause an increase in the running time by a logarithmic factor).
Additional Exercise 2
Define carefully a modified Turing machine in which the machine can,
in addition to altering the contents of a tape square,
delete an existing symbol (effectively removing the tape square
from the tape) or insert a new symbol (effectively adding a new
tape square to the tape). Be very specific about the transition
function of such a machine. Then show that such a machine can
be simulated by a conventional Turing machine with a quadratic
increase in running time.
Additional Exercise 3
Define a modified Turing machine model that is equipped with k
heads per tape for some constant k>1. Then show that a conventional
Turing machine can simulate a k-head Turing machine with at most
a quadratic increase in running time.
Give an example of a task for which a multihead Turing machine is much simpler
to design than a single-head one.
