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 string at the same time 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?
^ This paper ^ seems 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).