in Theory of Computation retagged by
827 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.
in Theory of Computation retagged by
827 views

2 Comments

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
0
should be c
1
1

1 Answer

7 votes
7 votes
Best answer

$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

2 Comments

edited by
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
0

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
1

Related questions