The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
5
-
1$\begingroup$ In the wikipedia article, DSPACE(..) only contains decision problems, not functions. If you replace "functions" with "languages" in your question, the answer is yes. $\endgroup$– phsMay 27, 2016 at 10:17
-
$\begingroup$ I don't understand the question. You seem to be asking, "does $A=B$ really imply $A \subseteq B$?". In the second part, you ignore that DSPACE(1) ⊆ PR ⊆ R (which also follows from DSPACE(O(1)) = REG), that is you are not asking anything new. Community votes, please: unclear? $\endgroup$– Raphael ♦May 27, 2016 at 12:05
-
$\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$– Raphael ♦May 27, 2016 at 12:06
-
$\begingroup$ Thanks for the feedback. I edited my question for clarification. I think the second part of the question was misleading, so I omit it. $\endgroup$– PeterMay 27, 2016 at 12:29
-
$\begingroup$ Are you sure about $DSPACE(O(1)) \subseteq PR$? A function in $PR$ is always computable, where a function in $DSPACE(O(1))$ could not be computable (e.g. endless loop). $\endgroup$– PeterMay 27, 2016 at 12:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation graph as one big finite automaton.
