Problem Detail: 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…
Asked By : zeb
Answered By : Peter Shor
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13988
