A Turning machine with insertion and deletion operations can be simulated by an ordinary Turing machine with a quadratic time cost. Do we know how insertion and deletion fit into the polynomial time hierarchy though?

In particular, does anyone know a quadratic single-tape Turing machine that cannot be simulated by a linear time single-tape Turing machine with insertion and deletion?

I've gathered that separation results are often more powerful, and maybe easier to prove, for the nondeterministic time hierarchy. Is that perhaps an easier place to attack this? If so, that's great because I'm ultimately most interested in rewrite systems anyways.

  • 2
    $\begingroup$ Perhaps the simple $L = \{ w\#w \}$ can be recognized by a single tape TM in $O(n^2)$ but not by a single tape ins/del TM in linear time $\endgroup$ – Marzio De Biasi Feb 6 '13 at 15:32
  • $\begingroup$ Palindromes, and equivalently $\{ w \# w \}$, are recognized by a linear-time single-tape nondeterministic Turing machine without insertions and deletions. Unsure without nondeterminism. Insertion and deletion can be simulated with a 2-dimensional tape, but that's something else entirely. $\endgroup$ – Jeff Burdges Feb 8 '13 at 15:30
  • 2
    $\begingroup$ it is a well know result that a deterministic single tape TM takes at least $O(n^2)$ steps to decide EQ and PAL (a classical application of communication complexity). $\endgroup$ – Marzio De Biasi Feb 8 '13 at 17:05
  • 1
    $\begingroup$ For what regards 1 tape nondeterministic TMs, their "power" depends on the definition of their running-time (see for example "Theory of One Tape Linear Time Turing Machines" ) $\endgroup$ – Marzio De Biasi Feb 8 '13 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.