More details on a language decided in $\Theta(\log \log n)$ space

Question

In Language with $\log \log n$ space complexity?, the following non-regular language is described:

$$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$

where $b(i)$ is the $k$-bit binary representation of $i$. This can evidently be computed in $\log \log n$ space, where $n$ is the length of the string, using the typical TM with input-output tapes.

This is apparently a common example used in complexity theory, however I would like some clarification on the method of calculation -- the answer given is very unclear and differs from the method defined in the reported source.

1. In the answer given, it says we do the check only when $m$ is smaller than the width of the first block. Am I misunderstanding this? If we do this, we never check the MSB of each representation, so for example the string $10\# 11 \# 10 \# 11$ would be accepted since it never checks $m=2$.

2. Do we check if the $m$ least significant bits form a counter modulo $m$, or modulo $2^m$? The lecture cited checks the ending modulo $2^m$, but the answer says modulo $m$. Wouldn't having a counter that goes up to $2^m$ take $m$ space which is already too much space ($m = O(\log n)$)? If we're supposed to make the counter modulo $m$, how do we take binary numbers modulo $m$ while still satisfying the space requirement? If $m$ is a power of two we can just do addition with overflow, but what about when it's not?I don't see an obvious, space-efficient algorithm for doing this in general.

3. Furthermore, even if we can do this in the given space, I don't see why the method taking modulo $m$ decides the language. For example, I can give you $00 \# 11 \# 10 \# 11$ and the LSBs form a counter "modulo $1$" and the two LSBs form a counter modulo $2$.

If anyone can clear up my questions that would be greatly appreciated. I think it's likely that there's just one thing I'm fundamentally misunderstanding about the presentation here which is causing everything else to not make any sense.

Answer 1

The trick here is to forget about the details as stated in the answer, and think about what would make the claim correct.

If $k$ were known, you could verify that the input is indeed $b(0)\#\cdots\#b(2^k-1)$ as follows: (below, a word is stuff between adjacent sharp signs)

1. The first word is $0^k$.
2. For any two contiguous words $x,y$, it holds that $y=x+1$.
3. The last word is $1^k$.

This can be accomplished in space $O(k)$.

Unfortunately, we don't know $k$ in advance, and even if we did, it's not necessarily the case that $k = O(\log \log n)$ – there could be much less than $2^k-1$ words. Therefore we use a slightly different approach. Let $K$ be the length of the first word. For each $t \leq K$, we verify the following:

1. The first word ends with $0^t$.
2. For any two contiguous words $x,y$, the $t$-bit suffixes $x',y'$ satisfy $y'=x'+1$ modulo $2^t$.
3. The last word ends with $1^t$.

If these tests pass for all $t \leq K$, then we accept the word. The $t$th test can only pass if the input is at least $(t+1)2^t-1$ symbols long and uses only $O(\log t)$ space, and this implies that the algorithm uses $O(\log\log n)$ space.