# Example of a simple recognizable language, whose complement is not recognizable

Can any one provide me with a simple language that is recognizable, but that it's complement is not?

I have read that recognizable languages may have this property but I am yet to find an example to think about. If you could provide the recognizable proof for both language and complement I would be very thankful, but just the language itself would be a nice help.

Thank you

• Be careful in your terminology, since "simple" also has a technical meaning in computability, e.g. simple set. Here I guess "simple" has the informal meaning of "easy to understand"."simple" with its technical meaning.
– chi
Jul 7 '16 at 11:05
• You are correct. I had the informal meaning in mind. Jul 7 '16 at 11:10

The set of recognizable languages whose complement is not recognizable is $RE\setminus R$. This holds since if $L,\overline{L}\in RE$, you can run the machines for $L,\overline{L}$ simultaneously and decide $L$. An example of a language in this set is the famous halting problem.

• That does make sense. In the complement of the halting problem, you would accept if the TM never halted right? You can say the TM halts if it ever halts, but if it never halts you cant say anything. So at most, the complement of the halting problem will only be able to reject. Does this reasoning make sense? Jul 7 '16 at 11:08
• @RicardoFerreiradaSilva No, it's just intuition. You don't necessarily have to run the machine in order to know whether it halts. Fortunately, one can prove that the non-halting problem is not recognizable. Jul 7 '16 at 11:36
• You are right. I did a proof where I assumed the non-halting problem was recognizable, this allowed me to construct a decidable halting problem, thus reaching a contraction. This also follows the propertie that says that if a language and its complementary are recognizable, then that language is decidable (which the Halting problem is not). Jul 7 '16 at 19:16