Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed under complementation?

Explanation also says,


This fails because $M$ only needs to halt if $w \in L(M)$ - doesn't have to say "no".

What does it mean?

The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- another proof may still work!

The problem is that flipping the result of a TM only works if you get a result; $\mathrm{RE}$ promises only an acceptor, not a decider, which may loop if the input is not in the language. Therefore, you can not flip properly; all you'd get is a machine that says "no" of the word is not the language but loops otherwise. That's a machine for $\mathrm{co\text{-}RE}$, not $\mathrm{RE}$.

As for why $\mathrm{RE}$ is not closed against complement, the site you link contains all the answers; let me reiterate.

• If $L$ and $\overline{L}$ are both semi-decidable, then both are decidable.

• Hence, if $\mathrm{RE}$ was closed against complement, we'd have $\mathrm{R} = \mathrm{RE}$.

• But we know that $\mathrm{R} \subsetneq \mathrm{RE}$ (by witness of the halting problem), so this can't be true.

StackExchange Computer Science Q#21284, answer score: 6