0
$\begingroup$

Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \sum^{\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?

$\endgroup$
  • $\begingroup$ What is "co-CE"? Or is it a typo? Also, is $G$ supposed to be a TM here? $\endgroup$ – dkaeae Dec 17 '18 at 7:12
0
$\begingroup$

If you by co-CE mean co-Computably Enumerable, then they are the same.

The field called Recursion Theory is also known as Computation Theory.

You find the same analogy in the classes. Recursive is a different way of calling Computable. A recursively enumerable set is a different way of calling computably enumerable set.

$\endgroup$
0
$\begingroup$

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

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

$\endgroup$

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.