Space complexity below $\log\log$

Question

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$.

It's well known fact in Space Complexity, but how to show it explicitly?

Answer 1

So here is the main idea behind this fact. Let us denote by $C$ all possible configuration of the $l(n)$-space bounded TM. Notice that $|C|\le 2^{c\cdot l(n)}$, where $c$ is a constant depending on $M$.

We assume that the input tape is a two-way tape. Let $w$ be a word of size $n$, such that for all smaller words $u$ we have $l(w)>l(u)$. When the head moves from position $i$ to position $i+1$ on the input tape, or vice versa, we record the current configuration of the computation in the crossing sequence $C_i$. Assume we have $i\neq j$ with $C_i=C_j$. Then we define as $w'$ the word obtained from $w$ by deleting everything between the characters number $i$ and $j$. We observe that $w'$ is a shorter word which uses the same amount of space. Contradiction, there is no such $w$.

If $l(n)\in o(\log\log n)$ then you have $o(\log n)$ configurations and $o(n)$ crossing sequences. Hence two crossing sequences are the same.

Notice that if your input tape is 1-way, then even with $o(\log n)$ space you are doomed.

Answer 2

The (I think) original proof is by Hartmanis, Lewis & Stearns, conveniently available for free :).

My rough understanding of it is that it goes via equivalence to the class of regular languages in the sense that you only need a constant amount of space to decide a regular language (just whatever state it's up to, basically), so they're decidable in $DSPACE(O(1))$, but if you want to decide anything non-regular, then you need $\Omega(\log\log n)$ space, so there's an "empty" gap, even with that extra bit of space ($o(\log\log n)$), it's so tiny that you can't do anything new with it.