Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?

Question

It is known that $\mathrm{SPACE}(o(\log \log n)) = \mathrm{SPACE}(O(1))$ (see e.g. these lecture notes by Christian Scheideler).

One inclusion is trivial, so I'm trying to show that $\mathrm{SPACE}(o(\log \log n)) \subseteq \mathrm{SPACE}(O(1))$ as follows.

Let $L$ be a language and $A$ is a Turing machine with alphabet size plus tape symbol is equal to $c$, to solve the problem $L$. We know that number of configurations is going to be at most $c^ {o(\log \log n)}\times\mathrm{poly} (o(\log \log n))$ (roughly), but even $c^ {o(\log \log n)} \notin O(1)$.

For example, $ s(n) = \log \log \log n \in o(\log \log n)$ but $c^{s(n)} \notin O(1) $. I don't know, how to proceed further.

My question: How to prove that $\mathrm{SPACE}(o(\log \log n))\subseteq \mathrm{SPACE}(O(1))$?

Answer 1

You're basically there. If the machine uses at most $s(n)$ tape cells for inputs of length $n$, then it can't visit more than $C(n)=|Q||\Sigma|^{s(n)}s(n)$ different configurations (possible states times possible tape contents times possible head positions). Since the machine decides a language, it must halt for all inputs, which means that it can't repeat a configuration, since a deterministic machine that repeats a configuration must loop forever. Therefore, by the pigeonhole principle, it can't run for more than $C(n)$ steps on any input of length $n$.

If $s\in o(\log\log n)$ then $C(n) = o(n)$ so the machine terminates after fewer than $n$ steps for all sufficiently large $n$. Intuitively, the machine can't stop in, say, $\sqrt{n}$ steps because, in that many steps, it hasn't seen the whole input, so it doesn't even know what $n$ is.

More formally, let $t(n)$ be the greatest number of steps taken by the machine on inputs of length $n$. Let $w$ be an input long enough that $t(n)<n$ for all $n\geq |w|$, and choose $w$ so that the machine runs for $t(|w|)$ steps on this input. We know that $t(|w|)\leq C(|w|)<|w|$, so the machine must terminate before it has time to read the whole input. Because it doesn't read the whole input, its execution on input $wz$ must be the same as its execution on $w$, for any string $z$. Therefore $t(|wz|)=t(|w|)$ for all strings $z$, so the function $t$ is constant for all inputs greater than length $|w|$.

Because it halts in a constant number of steps, it only uses a constant number of tape cells, so the language it decides is in $\mathrm{SPACE}(O(1))$.