patternMinor
TM recognizing $0^n1^n$ requires Ω(log n) space
Viewed 0 times
spacerequiresrecognizinglog
Problem
I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires
$\Omega(\text{log }n)$ space.
I believe this can be done using a crossing sequence argument.
I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.
What I have tried is:
Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$.
Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.
Let $C$ be the set of configurations of $M$ on $x$. That is, $C$ is the set of tuples of the form
(state, work tape head position, work tape contents).
Then $|C| \leq |Q_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.
The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations occurring as the input head moves across that boundary.
Each term of a crossing sequence can be any of the $|C|$ elements from $C$.
Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.
Therefore,
number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.
The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.
$\Omega(\text{log }n)$ space.
I believe this can be done using a crossing sequence argument.
I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.
What I have tried is:
Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$.
Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.
Let $C$ be the set of configurations of $M$ on $x$. That is, $C$ is the set of tuples of the form
(state, work tape head position, work tape contents).
Then $|C| \leq |Q_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.
The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations occurring as the input head moves across that boundary.
Each term of a crossing sequence can be any of the $|C|$ elements from $C$.
Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.
Therefore,
number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.
The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.
Solution
As you correctly point out by counting configurations, it holds that $SPACE[o(\log n)]\subseteq TIME[o(n)]$.
There is a theorem stating that $TIME[o(n\log n)]=REG$. See e.g. here.
If, by contradiction, we had $\{0^n1^n: n\in \mathbb{N}\}\in SPACE[o(\log n)]$, it would then follow that $\{0^n1^n: n\in \mathbb{N}\}\in REG$, which is clearly false.
Thus, $\{0^n1^n: n\in \mathbb{N}\}$ cannot be solved in $SPACE[o(\log n)]$.
There is a theorem stating that $TIME[o(n\log n)]=REG$. See e.g. here.
If, by contradiction, we had $\{0^n1^n: n\in \mathbb{N}\}\in SPACE[o(\log n)]$, it would then follow that $\{0^n1^n: n\in \mathbb{N}\}\in REG$, which is clearly false.
Thus, $\{0^n1^n: n\in \mathbb{N}\}$ cannot be solved in $SPACE[o(\log n)]$.
Context
StackExchange Computer Science Q#42835, answer score: 2
Revisions (0)
No revisions yet.