# 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. – Ricardo Ferreira da Silva 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.