patternModerate
Good way to describe co-RE (co-recursively enumerable)?
Viewed 0 times
wayrecursivelyenumerabledescribegood
Problem
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?
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?
Solution
The class ${\sf coRE}$ contains all languages whose complement is in ${\sf RE}$. Put differently:
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.
- 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.
Context
StackExchange Computer Science Q#13947, answer score: 16
Revisions (0)
No revisions yet.