Space complexity below $\log\log$

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?

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.

• Thank you very much for the answer, I am a little bit confused what is crossing sequence, according to wikipedia it is the sequence of the states (if it's so why $i \neq j$ with $C_i = C_j$). Could you please provide more details for the last statement with $o(\log n)$ configurations and $o(n)$ crossing sequences.
– com
Dec 14 '12 at 8:33
• A crossing sequence is a sequence of configurations of a TM. As explained in the answer: every time the head of the input tape moves between cell $i$ and $i+1$ you take the current configuration and append it to the sequence $C_i$. Regarding your second question. In the answer we discussed that there are $2^{cl(n)}$ configurations $C$, but since $l(n)=o(\log\log n)$ this means that you have $|C|=o(\log n)$. Now consider the number of all possible subsets of $C$, there are $2^{|C|}=o(n)$ many such subsets, hence there are $o(n)$ different crossing sequences. Dec 14 '12 at 9:25
• thank you for explanation, one more question, when the head move between cell $i$ and $i+1$, the current configuration goes to $C_i$, but theoretically head can move from $i$ to $i+1$ many times during the processing of TM so $C_i$ can have a lot of set. What can I say if $C_i=C_j$, I see a kind of redundancy (What can I state more formally?). Why having less that $n$ crossing sequence concludes that TM used the constant space?
– com
Dec 19 '12 at 10:49
• The crossing sequences are not sets, but sequences, if $C_i=C_j$ then you can cut the input between $i$ and $j$ and the computation would still fit together. Hence there is a shorter word accepted, using the same space. Dec 19 '12 at 12:07
• I could not follow your logic. I think you are missing crucial steps. Nov 10 '17 at 6:11

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.