1 votes 1 votes What is the complement of Non-Recursive Enumerable Language ? Theory of Computation theory-of-computation + – Rajesh Pradhan asked Dec 18, 2016 Rajesh Pradhan 385 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kapil commented Dec 18, 2016 reply Follow Share @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. 7 votes 7 votes Rajesh Pradhan commented Dec 18, 2016 reply Follow Share Thanks @Kapil ; Agree with U. Finally, The complement of NREL is (REL or NREL). 0 votes 0 votes sudsho commented Dec 18, 2016 reply Follow Share 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 :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes No one knows:) thor answered Dec 18, 2016 thor comment Share Follow See 1 comment See all 1 1 comment reply Rajesh Pradhan commented Dec 18, 2016 reply Follow Share Thanks for ur ans. can u plz give any reference wrt ur ans. 1 votes 1 votes Please log in or register to add a comment.