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$?

  • 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$ – phs May 27 '16 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 '16 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 '16 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$ – Peter May 27 '16 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$ – Peter May 27 '16 at 12:38

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.


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.