# Are all functions with constant space complexity in $REG$?

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

• In the wikipedia article, DSPACE(..) only contains decision problems, not functions. If you replace "functions" with "languages" in your question, the answer is yes. – phs May 27 '16 at 10:17
• 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? – Raphael May 27 '16 at 12:05
• 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! – Raphael May 27 '16 at 12:06
• Thanks for the feedback. I edited my question for clarification. I think the second part of the question was misleading, so I omit it. – Peter May 27 '16 at 12:29
• 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). – Peter May 27 '16 at 12:38