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.