2 votes 2 votes If $L$ is Turing-recongnizable. Then (A) $L$ and $\bar{L}$ must be decidable. (B) $L$ must be decidable but $\bar{L}$ need not be. (C) Either $L$ is decidable or $\bar{L}$ is not Turing recognizable. (D) None of above. Theory of Computation theory-of-computation recursive-and-recursively-enumerable-languages + – bahirNaik asked Jan 4, 2016 retagged Jul 4, 2017 by Arjun bahirNaik 812 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply focus _GATE commented Jan 4, 2016 reply Follow Share l is turing recogizable mens l is RE so its complemennt should be not RE a) option is false as for decidable both l and l' should be REC b) l cant be decidable as it outside rec which is only undecidable or partially decidable so false c) also false so i think d should be ans.?? 0 votes 0 votes Pooja Palod commented Jan 4, 2016 reply Follow Share should be c 1 votes 1 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes $L$ is r. e., $L'$ may or may not be r. e. If $L'$ is r. e. , then it means $L$ is decidable. If $L'$ is not r. e. , then it means $L'$ is not Turing Recognizable. Option $C$. Praveen Saini answered Jan 4, 2016 selected Jan 4, 2016 by bahirNaik Praveen Saini comment Share Follow See all 2 Comments See all 2 2 Comments reply Navnit Kumar 1 commented Apr 23, 2016 i edited by Navnit Kumar 1 Apr 23, 2016 reply Follow Share If L is Turing Recognizable then It does not mean that it will be decidable too. I think it will be partially decidable means It will halt if input is in the language and may or may not halt if it is not in the language. So, I thing (D) should be the answer. Kindly reply if I am wrong. 0 votes 0 votes Arjun commented Apr 23, 2016 reply Follow Share You are partially correct :) "I think it will be partially decidable means It will halt if input is in the language and may or may not halt if it is not in the language" This statement is correct. But this doesn't say that statement C is false, rt? 1 votes 1 votes Please log in or register to add a comment.