Can the complement of a non-recursive language be RE

I’ve got a problem where I need to check the validity (i.e to say whether it’s true or false) of the following statement:

Complement of a non-recursive language can NEVER be recognized by any turing machine.

How I’ve thought of this is that, if a language $mathcal{L}$ is non-recursive, there is no turing machine that accepts the language. That is, there’s no TM that halts for every string in $mathcal{L}$. But there could be a TM $M_1$ that halts for some of the strings in $mathcal{L}$.

Now suppose, the proposition is $ false$. So there could be a TM ${M_2}$ that recognizes the complement of $mathcal{L}$. So ${M_2}$ halts and accepts every string that is NOT in $mathcal{L}$ and may or may not halt for strings in $mathcal{L}$.

Intuitively, It appears that ${M_1}$ and ${M_2}$ could be same, which makes my assumption $ true$. That is the the proposition is $ false$.

But I’m not certain about the arguments I’ve made (as the equivalence of $M_1$ and $M_2$ is based on intuition). Can someone verify whether I’m correct or correct me otherwise.

Leave a Reply

Your email address will not be published. Required fields are marked *