1
$\begingroup$

Is the complement of a Non-Recognizable language

  1. Recognizable
  2. Non-Recognizable
  3. May be Recognizable, May be Non-recognizable. I.e cant comment.

A mathematical proof would be of great help since im unable to think of any way to prove this.

I did some research on this and found below examples. Im specifying complement using a "!"

  1. !A(TM) is a non-recognizable language while A(TM) is a recognizable language.
  2. EQ(TM) is a non-recognizable language and !EQ(TM) is also non-recognizable language

The above two would mean that we simply cant comment on the Recognizability of the complement of non-recognizable language. But I feel that there should be some way to prove (or disprove) this.

$\endgroup$
1
$\begingroup$

Assuming that you can prove statement 1 and 2 above, you have just presented a proof. You're trying to show that there exists a language which is non-recognizable such that its complement is recognizable. You then prove that $!A(TM)$ has this property. Then you want to show that there exists a non-recognizable language whose complement is also non-recognizable and then you show that $EQ(TM)$ has this property.

The point is that to prove that you can't comment, you need only to show that both possibilities are possible ie. that examples of each exist.

$\endgroup$
  • 1
    $\begingroup$ Just a note: point 1 is a direct consequence of the easy lemma: $L$ is decidable if and only if $L$ and $\bar{L}$ are recognizable. Point 2 can be proved using a Turing reduction from $EQ_{TM}$ to $\overline{A_{TM}}$ and from $\overline{EQ_{TM}}$ to $\overline{A_{TM}}$ $\endgroup$ – Vor Oct 19 '12 at 20:01

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.