Tape Reduction

Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoteric question, tape reduction plays an important role in time and space hierarchies and creating efficient reductions.

For space we have an easy result: Every k-tape s(n)-space bounded Turing machine can be simulated by a 1-tape machine in O(s(n)) space. Create a single supertape with separate "tracks" for each of the original tapes and add markers for the locations of the heads on each of these tapes.

For deterministic and nondeterministic time, this constructions yields a t²(n)-time 1-tape simulation of a k-tape t(n)-time machine and this is the best you can do (consider { x#x | x∈Σ^*}). We can do much better if we reduce k tapes to 2 tapes.

We can simulate any nondeterministic t(n)-time k-tape machine in nondeterministic O(t(n)) time on a 2-tape machine. Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

For deterministic time we can only achieve a weaker result: Every t(n)-time k-tape machine has a 2-tape simulation using O(t(n)log t(n)) time. The proof (due to Hennie and Stearns) is quite involved and I won't give it here. The proof has a nice side effect: The construction creates an oblivious machine where the head movements depend only on the input length. One can use this fact to show that we can simulate any t(n)-time Turing machines with O(t(n)log t(n))-size bounded fan-in circuits and reduce any t(n)-time nondeterministic computation to satisfiability questions of size O(t(n)log t(n)).