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...

  • $\begingroup$ In order to prove the $\Omega(n^2)$ lower bound you can use the lower bounds methods of Communication Complexity. For example you can easily adapt the proof that palindromes ($\{ww^R\}$) requires $\Omega(n^2)$, to your case. See exercise 13.2 of the Communication Complexity chapter of Arora and Barak, "Computational Complexity: A Moder Approach" $\endgroup$ – Vor Aug 28 '13 at 8:12
  • $\begingroup$ The hint for the exercise is incorrect: consider the Turing machine that simply copies the first n/3 bits into the middle area, then compares the middle area to the last n/3 bits. This machine only travels from location n/3 to location 2n/3 once. $\endgroup$ – zeb Aug 28 '13 at 9:58
  • $\begingroup$ I don't think it's wrong: given a string $w \#^n w^R$, $|w|=n$ (there are three "zones" of length n/3), if $k$ traversals of the $\#$ zone are enough to decide it, then there is a $O(k)$ protocol for the equality . In your case you should check the communication complexity of reversing the string $\{0,1\}^n \#^n \{0,1\}^n$. $\endgroup$ – Vor Aug 28 '13 at 10:33

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.

  • $\begingroup$ Ah, I think I finally understood how to do this rigorously. Essentially, you just need to show that the number of times the head takes a step from location k to location k+1 is at least min(k,n-k) divided by the logarithm of the number of states. $\endgroup$ – zeb Aug 30 '13 at 11:31

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.