Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
Maciej Liśkiewicz, Krzysztof Loryś · SIAM Journal on Computing · 1990
Every single-tape Turing machine (TM) of time complexity $T(n) \geqq n^{2}$ can be simulated by a single-tape TM in space $T^{{1 / 2}}(n)$. It is shown that the time of the simulation can be bounded by $T^{3/2}(n)$ in the case of deterministic TMs and by $T(n)$ in the case of nondeterministic ones. Similar results are shown for off-line machines and for machines with multidimensional tape.