GateForum Test Series: Theory Of Computation - Recursive and Recursively Enumerable Languages

Question

What is Turing Decidable and Turing Recognizable and What to conclude from those terms?

Comments

Gupta731 there must have been an option stating $L$ and $L'$ both are turing decidable

---

Turing recognizable means recursively enumerable language and turing decidable means recursive language.

---

No @Mk Utkarsh, This is all.

Answer 1

A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.

A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.

Comments

Thank you.

And how is the question related with the definitions, It's asking for complements.

---

Just take Turing Decidable as Recursive language and Turing recognizable as Recursively enumerable lang

which means  L is recursive = > L` is also recursive => L & L` are turing decidable => L & L`are turing recognizable.

So Option A

Answer 2

Option a is right

• If L is decidable then it is recursive language . 
• Recursive language is closed under complementation .
• So both L and L' are recursive language ( decidable).
• And every recursive language is also recursive ennum ( turing recognizable )