$\text{DSPACE}(O(1))=\text{REG}$ Proof?

Question

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?

Answer 1

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.