Speedup with multi-head Turing Machine

Question

What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits on different parts of the tape)?

ie. what is the overhead, worst-case, for a one-head Turing Machine to simulate a multi-head Turing Machine as the number of heads grow?

https://link.springer.com/content/pdf/10.1007/3-540-08342-1_35.pdf

^ This paper ^ says linear time. But the multi-head machines have the additional property of a one-move shift operation (shift a given head to the position of some other given head), is this standard?

Thanks!

Answer 1

First, the one-move shift is definitely NOT standard, but, as far as I understand, it only strengthens the result in that article. If a machine with the special operation can be simulated, then of course a machine without that operation can as well.

Second, here are some papers by Hans-Jörg Stoß dealing with multi-head machines. No one-move shifts here.

1. k-Band-Simulation von k-Kopf-Turing-Maschinen (1970) - establishes that $k$-head and $k$-tape can simulate each other without changing computation time.
2. Zwei-Band Simulation von Turingmaschinen (1971) - simulates a machine with $k$ heads on an $m$-dimensional tape by a machine with 1 normal tape plus 1 stack, establishing a rather precise time bound.
3. Linear-Time Simulation of Multihead Turing Machines (1989) - linearly simulates a machine with $k$-heads on a $d$-dimensional tape by a machine with $k$ separate $d$-dimensional tapes plus 1 normal tape.

Unfortunately, the first two are, as far as I know, only in German. The full text of the third one (translated) is here: doi.org/10.1016/0890-5401(89)90037-0