If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$

Question

I have been given an assignment that I'm having a very hard time understanding.

The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (so if the language is regular, the complexity is $O(\log \log n)$). The computational model to be used is a Turing machine with one input and one work tape.

Here's an excerpt from a book called Theory of computation by Dexter C. Kozen that I will be using to prove the assumption (if it's not allowed to post such an excerpt here please let me know, I'll remove it and share just some parts there instead, I posted it whole as I consider all information there to be important).

I have read this excerpt several times and there are several parts that I wasn't able to grasp. If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell. On the other hand, $\sum^{m}_{i=0} N^{i}$ is equal to crossing sequences on $m$ cells. So the thing I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \geq \Omega (\log \log n)$." I just don't understand how it's possible to come up with this equation by taking those three mentioned equations. The first step should be replacing $N$ in those equations, which gives me these two equations:

$\frac{n}{2} \leq \sum^{m}_{i=0} (q \cdot S(n)\cdot d^{S(n)})^{i} = \frac{(q \cdot S(n)\cdot d^{S(n)})^{m+1}-1}{(q \cdot S(n)\cdot d^{S(n)})-1}$

$m \leq 2 \cdot (q \cdot S(n)\cdot d^{S(n)})$

I don't know how to combine these two equations and reach the desired equation that is $S(n) \geq \Omega (\log \log n)$. Thank you for any help in advance.

Answer 1

If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell.

That's not accurate: a crossing sequence is a sequence of configurations. We form the crossing sequence at position $i$ as follows: we trace the execution of the Turing machine, and whenever the head on the input tape crosses the $i$'th position (either toward position $i+1$ or toward position $i-1$), we concatenate the current configuration (state, contents of work tape, and head location on work tape) to the crossing sequence.

On the other hand, $\sum_{i=0}^m N^i$ is equal to crossing sequences on $m$ cells.

No. That's the number of crossing sequences of length at most $m$ at a single cell.

I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?

Suppose that the crossing sequence $c$ occurs at position $i$. Then the crossing sequences at positions $1,\ldots,i$ are all distinct: if the crossing sequences at positions $j<k\leq i$ were identical, deleting the part of the input corresponding to positions $j+1,\ldots,k$ will result in a shorter input $x$ with the same crossing sequence $c$ (at position $i-(k-j)$. Similarly, the crossing sequences at positions $i,\ldots,n$ are all distinct. What we cannot say is that the crossing sequences at positions $1,\ldots,n$ are all distinct — the same argument doesn't work.

For the rest of the argument, we want to find as many distinct crossing sequences as possible. Therefore we take the maximum between $i$ (the number of crossing sequences corresponding to positions $1,ldots,i$) and $n-i+1$ (the number of crossing sequences corresponding to positions $i,\ldots,n$), which is always at least $n/2$.

One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \ge \Omega(\log\log n)$."

The equations in question state \begin{align} N &= qS(n)d^{S(n)} \\ \frac{n}{2} &\le \frac{N^{m+1}-1}{N-1} \\ m &\le 2N \end{align} The second equation simplifies to $$ n \leq 2N^{2m}. $$ Applying the third equation, $$ n \leq 2N^{4N}. $$ Taking logarithm, $$ \log n \leq 4N\log N + \log 2. $$ If $x \leq y\log y$ then $y = \Omega(x/\log x)$, and so $$ N = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Substituting the value of $N$, $$ qS(n)d^{S(n)} = \Omega\left(\frac{\log n}{\log\log n}\right). $$ Taking another logarithm, $$ \log q + \log S(n) + S(n) \log d \geq \log \log n - O(1). $$ Since $\log q + \log S(n) = o(S(n))$, the left-hand side is $O(S(n))$, and so $$ S(n) = \Omega(\log\log n). $$