College of Computer & Information Science Spring 2008 Northeastern University Handout 8 CSG714: Theory of Computation 11 February 2008

Problem of the Week – 5

Running times of Turing machines

We have seen several simulation results concerning Turing machines. For instance, we saw that a T (n)-time multi-tape Turing machine can be simulated by a single-tape Turing machine in time O(T (n)^{2}), if T (n) ≥ n. In these results, we have used the asymptotic notation liberally to hide multiplicative constants in the running time. The following exercises somewhat justify this practice when working with our models for the Turing machine and running time.

Prove the following simulation results.

(a) For any constant ε > 0, any single-tape Turing machine running in time T (n) can be simulated by a single-tape Turing machine running in time εT (n) + O(n^{2}).

(b) For any constants ε > 0 and k > 1, any k-tape Turing machine running in time T (n) can be simulated by a k-tape Turing machine running in time εT (n) + O(n).

(Hint: Enlarge the state space for the simulating Turing machine and simulate multiple steps at a time.)