2,604 views
4 votes
4 votes
If L is Turing-recognizable. Then
(a) L and ̅L must be decidable.
(b) L must be decidable but ̅ L need not be.
(c) Either L is decidable or ̅ L is not Turing recognizable.
(d) None of above.

3 Answers

3 votes
3 votes

Turing Recognizable: 

Let's check it:

If L is CSL : It is turing recognizable as well as turing decidable

If L is RE : It is turing recognizable but may not be turing decidable.

Complement of CSL is CSL, but complement of RE may or may NOT RE.

(a) L and ̅L must be decidable. - CSL satisfies but RE not 
(b) L must be decidable but ̅ L need not be. - Neither CSL nor RE satisfies
(c) Either L is decidable or ̅ L is not Turing recognizable. CSL not satisfies but RE satisfies
(d) None of above.

Answer should be C

0 votes
0 votes

A) correct answer 

both L L' are decidable hence both  will be TURING RECOGNIZABLE.

0 votes
0 votes

Option - (C)

A Language is said to be Turing Recongnizable it means, there exist an algorithm which can accept, any strings from this language if it is present in it, but it can stricly rejected the string,

MEAN IT's Non Halting Turing Machine Problem

Now,

Options A and B ) L Must be decidable.(not neccesary)

Option C)  Let say, in first case if L  is decidable then  ̅L is also decidable and therefore  ̅L is turing recongnizable now, in second case let say  ̅L is not turing recognizable that means there is no algorithm exist which can accept or reject this language and therefore, L is also undecidable here.

No related questions found