_/\_Doubt_/\_

Question

What is the complement of Non-Recursive Enumerable Language ?

Comments

@Rajesh

It is not closed for sure as Acceptance problem is NON RE and its complement (Halting Problem) is RE . 

---

Take one more language,

$L= \{\langle M \rangle\mid L(M) = \Sigma^*\}$ = NON RE

and its complement $L'= \{\langle M \rangle\mid L(M) != \Sigma^*\} $ is also NON RE

---

Take again one more language,

$$L = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

It is surely NON RE as both halting problem and its complement both are used and its complement is also same and even NON RE.

---

---

 

---

Thanks @Kapil ; Agree with U.

Finally, The complement of NREL is (REL or NREL).

---

non recusively enumerable...till recursively enumerable languages we have an enumeration procedure...TM can't enumerate all the languages of sigma star...possibility is that non recursively enumerable language is either recursive or beyond the decidability domain...if it lies within recursive...its compliment is recursive and hence recursively enumerable...if it lies outside the domain of TM..it may belong to undecidable class...here its compliment will be non recursively enumerable...this question is itself undecidable i guess :)

Answer 1

No one knows:)

Comments

Thanks for ur ans.

can u plz give any reference wrt ur ans.