1 votes 1 votes Theory of Computation decidability + – Prince Sindhiya asked Jan 20, 2019 Prince Sindhiya 458 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply anjali007 commented Jan 20, 2019 reply Follow Share D? 0 votes 0 votes Vaibhav Rai commented Jan 20, 2019 reply Follow Share option C 4 votes 4 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes $X$ is recursive $\implies \bar X$ is also recursive. $Y$ is r.e. but not recursive $\implies \bar Y$ is not even r.e. $\bar X$ reduces to $W \implies $ $W$ is recursive or a super set of it. $\bar Y$ reduces to $Z \implies $ $Z$ is not even r.e. Correct Answer: C. https://gatecse.in/some_reduction_inferences/ Arjun answered Aug 12, 2019 • selected Aug 14, 2019 by Prince Sindhiya Arjun comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Compliment(REC)=REC X=REC Compliment (RE but recursive) = RE Compliment (RE but not recursive) = Not RE Y=RE but not REC i.e W=Compliment(X)=REC Z=Compliment(Y)=Not RE D) is correct Ravi kumar singh answered Jan 20, 2019 Ravi kumar singh comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes x complement recursive and y complement not RE hence option D SUNNY054 answered Jan 21, 2019 SUNNY054 comment Share Follow See all 0 reply Please log in or register to add a comment.