Good way to describe co-RE (co-recursively enumerable)?

Problem Detail: 

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?

Asked By : AC9000

Answered By : A.Schulz

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13947