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.
From your question I believe there is some confusion of the terms being used here. A recognizable language L is one such that a turing machine exists accepting it,  halting on every yes instance. There are also co-recognizable languages, those are languages whose complements are recognizable. Now, if a language happens to be both recognizable and co-recognizable, it is recursive, or decidable (why?). So a language can be non-recursive, but it may still be recognizable or co-recognizable. What can you say about the emptiness problem for turing machines $E_{TM} = \{\left &lt; M \right &gt;\ :\ \mathcal L(M) = \varnothing\}$ ?