Matching upper and lower bounds for simulations of several tapes on one multidimensional tape

摘要

we prove a THETA (t(n) d sq root t(n)/log t(n)) 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>=2. The lower bound holds for the problem of recognizing languages on machines with a separate one-way input tape.