Can the complement of a non-recursive language be RE

Question

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.

Answer 1

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 < M \right >\ :\ \mathcal L(M) = \varnothing\}$ ?

Answer 2

The given statement can be proven false by the following example:

The emptiness problem for a TM is non-recursive(even non-recognizable) but it's complement is recognizable.

$\qquad E_{TM}$ = {$\langle M \rangle$ | $M$ is a TM and $L(M) = ∅$}

$\qquad E_{TM}^c$ = {$\langle M \rangle$ | $M$ is a TM and $L(M) \neq ∅$}

$E_{TM}$ - Set of all TM's that accept nothing.

$E_{TM}$ - Set of all TM's that accept something.