6
$\begingroup$

I get that R is a set of languages that are decidable by a Turing Machines

And that RE is a set of languages that a each language can be recognized by a TM, that is the machine will halt when given a word from that language and loop otherwise.

But I can't wrap my head around co-RE. Is there a good way to describe it? A good example to convey what it really means?

$\endgroup$
11
$\begingroup$

The class ${\sf coRE}$ contains all languages whose complement is in ${\sf RE}$. Put differently:

  • A language $L$ is in ${\sf RE}$ if there exists a Turing machine that can check if a requested word $w$ is contained in $L$ for every word $w\in L$. The machine always tells the truth but it may cycle on inputs $w\not\in L$.
  • A language $L$ is in ${\sf coRE}$ if there exists a Turing machine that can check if a requested word $w$ is not contained in $L$ for every word $w\not\in L$. The machine always tells the truth but it may cycle on inputs $w\in L$.

An example: The language $\{ \langle M,w \rangle \mid \text{$M$ cycles on input $w$}\}$ is in ${\sf coRE}$. Just take a Turing machine that simulates $M$ on $w$ and rejects, whenever the simulation stops.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

The definitions are complementary, literally.

  • $\mathsf{RE}$ means that there is an algorithm that can (always) answer "Yes" (correctly) after finite time but maybe not "No".

  • $\mathsf{coRE}$ means that there is an algorithm that can (always) answer "No" (correctly) after finite time but maybe not "Yes".

You can think of $\mathsf{coRE}$ as recursively enumerating the complement (hence the name). From this you also see that $\mathsf{R} = \mathsf{RE} \cap \mathsf{coRE}$.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

It means that the complement of the language is recursively enumerable. In other words, while you can't enumerate the strings that are in the set, you can list all the languages that aren't in the set.

The language of encodings of Turing machines that halt on an empty tape is recursively enumerable; we could write a Turing machine that eventually prints every Turing-machine encoding that halts. For Turing machines that don't halt, however, we're out of luck; we don't have a way to know that a given encoding represents a Turing machine that will run forever. The set of encodings of Turing machines that don't halt is not recursively enumerable.

However, the set of encodings of Turing machines that don't halt when given the empty tape as input is a co-recursively enumerable set. We can write a Turing machine which eventually prints out every encoding which fails to belong to the desired set. Indeed, this is the same Turing machine that we discuss in the previous paragraph. Indeed, if $L \in {\sf RE}$, then $L^C \in {\sf coRE}$, and vice versa.

To see how it all fits together, if we have a language that is both ${\sf RE}$ and ${\sf coRE}$, the language is also ${\sf R}$, and vice versa. Suppose the language is is both ${\sf RE}$ and ${\sf coRE}$. Then we have Turing machines $M_{{\sf RE}}$ and $M_{{\sf coRE}}$ which enumerate all words belonging to, and not belonging to, the language, respectively. To positively determine whether a given word is or isn't in the language, then, we can simply run both machines at the same time, and wait for one of the machines to list our query. If our language is ${\sf R}$, we can make a machine to enumerate it or its complement by checking all Turing-machine encodings, and either skipping or emitting each one depending on whether or not it's in the language (which we can definitively answer, based on the assumption that the language is recursive, meaning we have a Turing machine to decide it).

The example of "encodings of Turing machines that don't halt" is a little contrived, but there's no reason that there couldn't be more natural sounding languages that are ${\sf coRE}$ by themselves.

| cite | improve this answer | |
$\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.