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?


Suppose you have a Turing machine with an $n$ sized tape with $k$ symbols and $s$ states. This system, as a whole, then has $s\cdot k^n \cdot n$ possible states it can be in ($s$ states, $k^n$ tape contents, $n$ tape head positions).

By definition $k$ and $s$ must be $O(1)$. If $n$ also is however, then the entire expression $s \cdot k^n \cdot n$ is a constant, and we can construct a finite state machine with that many states that has exactly the same behavior as the Turing machine.

  • $\begingroup$ Thank you for your answer, but maybe you didn't get where I am trapped, as expressed in the problem details. You constructed a turing machine that has finite state, and doesn't modify the tapes. However, it's still not a finite automaton, as it may choose to move its pointer right or left, where an DFA/NFA won't look back. $\endgroup$ – GZZ May 29 '20 at 15:33
  • $\begingroup$ @GZZ Sorry, I forgot one critical piece of information in the answer: the tape head position. That is also included in the state, but it only increases the state size by a constant. $\endgroup$ – orlp May 29 '20 at 17:23
  • $\begingroup$ I know that I can record the tape head position in states. But the states may still choose to move its tape head position left or right, while a DFA/NFA would read characters and move to next state according to a transition function, and always keep finite information of the prefix of the string having seen. Could you please specify the transition function $\delta: Q\times\Sigma\to Q$ of the finite automaton that is constructed from the TM? $\endgroup$ – GZZ May 30 '20 at 2:15
  • $\begingroup$ @GZZ Note that the Halting problem is decidable for finite-tape Turing machines. There are no infinite loops possible because the number of possible states is finite - the machine either halts or loops, provably. So for each possible input check whether the Turing machine halts and accepts or loops/rejects. This gives you a lookup table from input to accept/reject. Then one can make a DFA that has $1 + k + k^2 + \cdots + k^n$ states, one for each possible input string, and mark those states as accepting or not according to our lookup table. $\endgroup$ – orlp May 30 '20 at 4:52
  • 1
    $\begingroup$ I've marked the answer as accepted. Though I still do not understand something. This time I would try to make it more clear. When we consider problems concerning DSPACE(o(n)) (for example, DSPACE(O(1))), we assume that there are two tapes in that TM, an input tape that contains the problem to solve and is read only; and a writable tape that is of finite length (as you denoted $n$). To record the head position of the second tape we just need to encode the finite possibilities. But we are not able to record the head position of the first tape. The length of this tape is not finitely bounded. $\endgroup$ – GZZ Jun 1 '20 at 9:58

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.