retagged by
812 views
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.
retagged by

1 Answer

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$. 

selected by

Related questions

17 votes
17 votes
2 answers
2
gatecse asked Aug 20, 2014
2,331 views
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $A. $L$ is RE but $L'$ is not REB. Both $L$ and $L'$ are REC. $L$ is not RE but $L'$ is RED. Both $L$ and $L'$ are not RE...
17 votes
17 votes
4 answers
3
gatecse asked Aug 20, 2014
5,640 views
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
0 votes
0 votes
0 answers
4
sripo asked Jan 5, 2019
521 views
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.