2
$\begingroup$

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and know that the idea is to encode the finite possibilities of memory as finite states, and also have read https://cs.stackexchange.com/a/57938/112750 . However, I still have a question that I'm unable to answer. A finite automaton needs to read the characters one by one and never look back, but a TM, though restricted to use only $O(1)$ memory, may choose to go back and forth on its input tape. How can I eliminate this kind of looking back problem and construct an automaton that is equivalent to this TM?

$\endgroup$
2
$\begingroup$

There are several ways of showing this, but really there is only one core argument that needs to be understood, and that is the proof that 2-way DFAs are equivalent to DFAs.

A 2-way DFA (https://en.wikipedia.org/wiki/Two-way_finite_automaton) can go back and forth on its input tape, so it does not have to read the word from left to right. There are several beautiful proofs showing the equivalence of this model to standard DFAs. The basic idea is to use the notion of crossing sequences. You can easily find the proof online, so I'm omitting it from this answer.

Once you have this result, it's enough to show that $DSPACE(O(1))$ can be captured by a 2-way DFA. This is quite straightforward: a $DSPACE(O(1))$ TM has a read-only input tape, and a bounded size work tape. By replacing the bounded work tape with finitely many states (each capturing the entire contents of the work tape, as well as the location of the head and the state of the machine), you obtain an equivalent 2-way DFA, and you're done.

Another way of going about this, is to use the fact that with $O(1)$ space on the work tape, a halting TM can only work for $O(n)$ time, since the number of configuration basically boils down to the location of the reading head. Thus, $DSPACE(O(1))\subseteq TIME(O(n))$, and since $TIME(o(n\log n))=REG$, you obtain the result. The proof of the latter containment also makes use of crossing sequences, so it's fundamentally the same argument.

$\endgroup$

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.