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))$?


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

| cite | improve this answer | |
  • $\begingroup$ I'm confused - won't the position of the read only tape also count towards the number of configurations? For example, when deciding the language w1, where w is any word, the machine can just go until it reaches the last non blank spot? This requires constant space, but takes linear time. $\endgroup$ – Lorenzo Najt Jan 10 at 5:46
  • $\begingroup$ Although configurations is still taken to ignore the location of the read only head, the proof here en.wikipedia.org/wiki/DSPACE fixes that issue by using crossing sequences instead. $\endgroup$ – Lorenzo Najt Jan 10 at 23:33

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.