#undecidability

Question

why recursive enumerable languages does not satisfy the complementation property ???

Answer 1

First keep this things in mind that

1.If a language $L$ and its complement $L^{'}$ are recursive enumaerable then $L$ is recursive.
2.The complement of recursive language is recursive.

3.Recursive langauge(rec) are decidable

4. Recursive enumerabale(RE) language are semidecidable.

---

Let $L=$Recursive Enumerable language be closed under complementation.

Then $L$,$L^{'}$ will be RE  and hence $L$ will be Rec (point -1) and thus decidable (point -2)but $L$ is semidecidable (point -4), a contradiction!

Comments

What do u mean by semi decidable?

---

Correct me if I'm wrong @Anand.

If a recursively enumerable language isn't accepted by a TM then it might run forever or end with a result NO. On complementing this TM if we pass the same language it should say YES. If this was possible then we have a membership algo for REL which is not possible. Hence undecidable.

---

So a semi-decidable language cannot be decidable?

---

@Arjun sir I think what he meant was that since recursively enumerable languages which aren't accepted by TM on giving it to a TM will either go into infinite loop or will say Not Accepted. That is the reason he said it was semi-decidable which isn't used to describe it.