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 $win L$. The machine always tells the truth but it may cycle on inputs $wnotin 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 $wnotin L$. The machine always tells the truth but it may cycle on inputs $win 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
