[37] We analyze the speed of copying strings for Turing machines with a two-way input tape and one or more work tapes.

(a) Show that such a Turing machine with one work tape can copy a string of length s, initially positioned on the work tape, to a work tape segment that is d tape cells removed from the original position in O(d + sd/ log min(n, d)) steps. Here n denotes the length of the input.

(b) Show (by the incompressibility method) that the upper bound in Item

(a) is optimal. For d = Ω(log n), such a Turing machine with one work tape requires Ω(sd/ log min(n, d)) steps to copy a string of length s across d tape cells.

(c) Use Item

(a) to show that such Turing machines can simulate f(n)-

time bounded multitape Turing machines in O(f(n)2/ log n) steps. This is faster by a multiplicative factor log n than the straightforward simulations.

Comments. Source: [M. Dietzfelbinger, Inform. Process. Lett., 33(1989/

1990), 83–90].