$\log n$ lower bound for space complexity

Question

I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following:

Since the TM's work tapes are separated from its input tape, it makes sense to consider space-bounded machines that use space less than the input length, namely, $S(n) < n$. This is in contrast to time-bounded computation, where $\mathbf{DTIME}(T(n))$ for $T(n) < n$ does not make much sense since the TM does not have enough time to read the entire input. We will require however than $S(n) > \log n$ since the work tape has length $n$ [my highlight], and we would like the machine to at least be able to "remember" the index of the cell of the input tape that it is currently reading.

I doubt that the highlighted statement is true. As you can see, it says that to be able to remember the indexes of input tape, so

“Since the work tape has length $n$”

could not be true and it should be

“Since the input tape has length $n$”

If this is not a typo, I am confused why it mentions that the work tape has length of $n$, as we know that it may have smaller length.

Answer 1

Congratulations! You have found a typo in Arora and Barak's long textbook. There are likely many more.

Arora and Barak are not completely correct that the regime $S(n) \leq \log n$ is not interesting. In fact, what we do know is that the regime $S(n) = o(\log\log n)$ is not interesting, since Turing machines using that much space can only accept regular languages, and so can be modified to use no space at all. See for example this question.

The bound $\log\log n$ is tight here, in the sense that there is a non-regular language which can be accepted in space $O(\log \log n)$, namely the language consisting of all words of the form $$ 0\#1\#10\#11\#100\#\cdots\#\mathrm{bin}(m), $$ where $\mathrm{bin}(m)$ is the binary representation of $m$, which has length $O(\log m)$. This language can be accepted in space $O(\log\log m)$ (we only need to index words of length $O(\log m)$), whereas the input length is $\Omega(m)$. This example is taken from Michel's survey of space complexity, where it is attributed to Wagner and Wechsung, Computational complexity.