I have been stuck on this problem for a while:

Show that $L=\{\langle M \rangle : L(M) \text{ contains an even number of strings} \}$ is not Turing-recognizable.

I know that by Rice Theorem, this language is not decidable, which means either $L$ or $\overline{L}$ is not recognizable. But it appears to me that showing $\overline L$ is recognizable is not easier. Any help would be appreciated.


marked as duplicate by Raphael Nov 21 '18 at 0:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "which means either [L or its complement] is not recognizable" -- it can be the case that neither is! And that seems very likely here, since "even number" and "odd number" should, intuitively, equally hard to check. $\endgroup$ – Raphael Nov 21 '18 at 0:37
  • $\begingroup$ Hint: Reduce from the complement of the halting problem. Or, more boringly, try to apply the extended theorem of Rice -- always a good idea to try out first! $\endgroup$ – Raphael Nov 21 '18 at 0:45