Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones

Maciej Liskiewicz, Krzysztof LorysSIAM Journal on Computing 1990 · DOI · OpenReview

Abstract

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.
BibTeX
@article{liskiewicz1990fast,
  author = {Maciej Liskiewicz and Krzysztof Lorys},
  title = {{Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones}},
  journal = {SIAM Journal on Computing},
  year = {1990},
  doi = {10.1137/0219034},
}

Loading related content...

Figure