0 votes 0 votes Theory of Computation theory-of-computation decidability + – Na462 asked Jan 21, 2019 Na462 722 views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Na462 commented Jan 21, 2019 reply Follow Share According to me answer should be None of these. Question said that it can be arranged in a order now its countable set (of course) if they had said that it can be arranged in lexicographic order then we could have said it as Recursive, so now according to it if u see we will get Answer as NONE OF THESE but its not the answer :/ 0 votes 0 votes Shobhit Joshi commented Jan 21, 2019 reply Follow Share I am also getting D. What is the explanation 0 votes 0 votes Na462 commented Jan 21, 2019 reply Follow Share It should be D. because say a TM that accepts all rational numbers. Now its a countable set but i cant say it as recursive can i ? The proper interpretation should be that its a recursively enumerable language. Correct me if i am wrong. Answer is C 0 votes 0 votes Shobhit Joshi commented Jan 21, 2019 reply Follow Share $M$ is reducible to $L$, so $M$ can also be recursive. Isn't it ? 0 votes 0 votes Na462 commented Jan 21, 2019 reply Follow Share Yeah it can be recursive, there's a difference b/w can and will right ? Because i will think by taking worst case wouldn't i brother ? 0 votes 0 votes Shobhit Joshi commented Jan 21, 2019 reply Follow Share I thought the same as you didn't read your comment clearly. I think the answer should be $D$, but by proper order can they mean lexographically ? 0 votes 0 votes Na462 commented Jan 21, 2019 reply Follow Share No, every proper order is not lexicographic, because say the alphabet consist of {0,1} then ? or any other order could have been used. 0 votes 0 votes Shobhit Joshi commented Jan 21, 2019 reply Follow Share then it should be $D$ 0 votes 0 votes Na462 commented Jan 21, 2019 reply Follow Share i saw your comment i just wanna see that wether you agree with my reason :p 0 votes 0 votes Magma commented Jan 21, 2019 reply Follow Share yeah D but I have small doubt In option C also...can you explain why it's not correct ?? 0 votes 0 votes Shobhit Joshi commented Jan 21, 2019 reply Follow Share $M$ is reducible to $L$, so $M$ can be recursive enumerable. So, $M\bigcap L$ is not recursive always. Correct me if i'm wrong. 1 votes 1 votes Na462 commented Jan 21, 2019 reply Follow Share See we get that L is R.E.L and may or may not be Recursive though Now if M <= L (Say L i assumed as Recursive) then M will also be recursive then : M intersection L = Recursive intersection Recursive = Recursive If I assume L as Recursively enumerable but not recusive and M is reducible to L them M can be recursive So M intersection L will be Recusively enumerable not recursive 1 votes 1 votes Magma commented Jan 21, 2019 reply Follow Share thanks 1 votes 1 votes Please log in or register to add a comment.