# Why isn't the class of Turing-Recognizable languages closed under Complement?

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations to show how T-Recognizable languages are closed for Union, Intersection, Concatenation and Kleene Star.

Now I'm trying to answer a question to show why the classe of T-Recognizable languages are not closed for the operation of Complementation, but I cannot understand it. Could someone please explain this?

• First of all, what standard textbooks on this topic have you looked at? Every one of them is going to have a proof. – Andrej Bauer Apr 7 '13 at 17:53

Hint: Suppose it was. Let $L$ be a recognizable language and let $\overline{L}$ be its complement. If $\overline{L}$ was recognizable as well, let $M_1$ and $M_2$ be recognizers of $L$ and $\overline{L}$, respectively.
Can you now use $M_1$ and $M_2$ to construct a decider for $L$? What does this mean for undecidable and recognizable problems like the halting problem?
Intuitively, a TM $M$ can recognize $L$ if you run it on $\sigma \in L$ it will eventually halt and say "Yes"; there is no way of knowing if when run on $\sigma' \not\in L$ it will ever halt.