Decidability

Question

Consider a language L and its Complement L'  and the statements with reference to L.

       S1: If L is undecidable then L'(i,e, L complement) may or may not be undecidable.

Whether S1 is True of False. Please provide detailed explaination.

Answer 1

Undecidable means not recursive language ie RE but not Recursive and hence complement of RE but not Recursive  always not recursive which is RE but not Recursive and hence Undecidable.

So if L is Undecidable its complement is also Undecidable.

Comments

See, decidable languages are recursive languages. Hence Undecidable languages will be not recursive which is recursively enumerable but not Recursive.

So complement of recursively enumerable languages will be either recursive enumerable or not even recursively enumerable and in both the cases it remains to be Undecidable.

---

Thanks bro

---

Any day, man!