Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
We prove an O(t(n)(d)root t(n)/logt(n)) time bound for the simulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, d greater than or equal to 2. We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape.
lower bounds simulation computational complexity d-dimensional turing machines kolmogorov complexity