1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chi Jul 7 '16 at 11:05
  • $\begingroup$ You are correct. I had the informal meaning in mind. $\endgroup$ – Ricardo Ferreira da Silva Jul 7 '16 at 11:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ricardo Ferreira da Silva Jul 7 '16 at 11:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Jul 7 '16 at 11:36
  • $\begingroup$ 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). $\endgroup$ – Ricardo Ferreira da Silva Jul 7 '16 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.