# Need help understanding what co-recursively enumerable means

Lets say I have a set: $$L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not halt on inputs in L.

So in this case would something "not in L" be nothing?

• What is "co-CE"? Or is it a typo? Also, is $G$ supposed to be a TM here? – dkaeae Dec 17 '18 at 7:12
• A language is coRE, by definition, if its complement is RE. – Yuval Filmus Oct 14 '19 at 11:09
• @dkaeae Annoyingly, computability theory has a lot of duplicate terminology: "c.e.," "r.e.," "semidecidable," "recognizable," etc. all mean the same thing (at least in classical computability). "Co-c.e." (or "co-CE") means the same thing as "co-r.e." – Noah Schweber Oct 14 '19 at 16:30

No. A string $$\langle G\rangle$$ is not in $$L$$ means $$L(G)\ne \Sigma^*$$. Such strings exist of course. For example, if $$G$$ is a machine that rejects anything, then $$L(G)=\emptyset$$, thus $$\langle G\rangle\notin L$$.