Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

Question

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes).

The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s terminated by an end-of-string character. The tape head starts at the beginning of the string. The goal is for the tape to contain the original string in reverse order, terminated by an end-of-string character, with the tape head returned to the beginning of the string when the Turing machine finally halts.

The Turing machine can use as large an alphabet as we like (so long as it contains $0$, $1$, and an end-of-string character), and can have as many states as we like. Is there a fixed Turing machine that can complete this task in time $o(n^2)$?

It's easy to do this in time $O(n^2)$ using just a few states and symbols. It seems intuitively clear that something prevents us from doing it more than a constant factor faster, but I've never been able to prove it, and I often worry late into the night about miraculous applications of network coding or voodoo magic that somehow get a logarithmic speedup...

Answer 1

The standard way to prove things like this is to show that $\Theta(n)$ bits of information must cross at least $\Theta(n)$ points.

That is, if you're reversing it "in place", the first third of the bits must cross all $n/3$ middle cells and end up in the last $n/3$ cells. Since the head moves $O(1)$ bits a distance at most $1$ cell each step, this requires $n^2/9$ steps. If the reversed copy ends up in a different set of cells, a very similar argument gives an $\Omega(n^2)$ lower bound.

It takes some work to make this intuitive idea rigorous, but it has been done, although I don't have enough time to locate the papers these results appeared in. If anybody can point to a relevant paper, please edit this answer to do so.

Answer 2

I don't see any way to do it, either.

It seems to take $\Theta(n^2)$ time just to make a second copy of the string (e.g., if the input is the $n$-bit string $s$, at the end of the computation we want the tape to contain the string $ss$). Maybe this could be formalized somehow using the methods of communication complexity; I don't know.

Here's some intuition for why reversal feels like it should require $\Omega(n^2)$ steps. Color bit positions $0,1,\ldots,n/2$ of the tape green; that's "the green zone". Similarly, let's treat bit positions $3n/4,\dots,n$ as "the red zone". Intuitively, we have to convey $n/2$ bits of information from the green zone to the red zone. If the finite-state automaton of the Turing machine can hold $b$ bits of information, then the Turing machine will have to visit the green zone $n/(2b)$ times, and then it'll have to travel at least $n$ positions to get to the red zone. Thus, it feels like the Turing machine is going to have to do at least $n/(2b)$ passes (where in each pass it enters the green zone, then travels from the green zone to the red zone), and each pass will take $n$ steps just for the head movement, for a total of at least $n^2/(2b)=\Omega(n^2)$ steps. This is not a complete proof, but it seems to give some sense of why I don't expect there to be a faster way to do it.