0
$\begingroup$

Can someone please tell me if complement of halting problem(L) is Co-RE or non R.E ?

I think that it is Co-RE as L' (L complement) is R.E but everywhere its given non R.E

$\endgroup$
  • $\begingroup$ Have you tried proving your claim? There's a one-line proof (assuming one Lemma with a simple proof). $\endgroup$ – Raphael Nov 13 '17 at 6:48
  • $\begingroup$ In the duplicate link its mentioned not R.E . But halting problem is R.E so its complement should be co-R.E right? $\endgroup$ – Rajesh R Nov 13 '17 at 6:50
  • 1
    $\begingroup$ Being non-RE and co-RE are two separate things that are not mutually exclusive. One is trivial, the other potentially not. $\endgroup$ – Raphael Nov 13 '17 at 6:52
  • 1
    $\begingroup$ As I've been trying to tell you, it can be both. $\endgroup$ – Raphael Nov 14 '17 at 8:24
  • 1
    $\begingroup$ No; check the definitions. It's not about individual machines, but problems (that is the existence of certain machines, which does not preclude other machines). The complement of the Halting problem/language is, famously, not r.e. but co-r.e.. $\endgroup$ – Raphael Nov 18 '17 at 17:18