<p>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?</p>

<p>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?  </p>

<p>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. </p>

CC BY-SA 3.0
2013-02-06T15:32:51.293Z
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
Marzio De Biasi
CC BY-SA 3.0
2013-02-08T15:30:44.193Z
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.
Jeff Burdges
CC BY-SA 3.0
2013-02-08T17:05:45.417Z
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](http://www.cs.princeton.edu/courses/archive/spr08/cos598D/communicatechap.pdf)).
Marzio De Biasi
CC BY-SA 3.0
2013-02-08T18:00:37.693Z
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"](http://arxiv.org/pdf/cs/0310046.pdf) )
Marzio De Biasi
<time-complexity><turing-machines><term-rewriting-systems>
Insertion and deletion operations for Turing machines
Jeff Burdges
# Insertion and deletion operations for Turing machines

(Asked by: username_0 on 2013-02-06)

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.

**Tags:** time-complexity, turing-machines, term-rewriting-systems

> **Comments:**
> **username_1**: 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  
> **username_0**: 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.  
> **username_1**: 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](http://www.cs.princeton.edu/courses/archive/spr08/cos598D/communicatechap.pdf)).  
> **username_1**: 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"](http://arxiv.org/pdf/cs/0310046.pdf) )  

---

## 0 answers

