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.


2 Answers 2


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\}$ ?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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