I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have a look and give me some feedback?

I have the following decision problem and I want to show that it is not semi-decidable:

$H'=\{\langle M\rangle \mid \text{ M does not halt on } \langle M\rangle\}$

My solution so far is as follows:

Suppose $H'$ is semi-decidable, then there exists a TM $M_{H'}$, which semi-decides $H'$. This means that for all $x \in H'$, $M_{H'}$ accepts $x$, and for all $x \notin H'$, $M_{H'}$ halts without accepting or $M_{H'}$ enters an infinite loop.

I know this is not a valid proof and I also know that I have to show the contradiction, but I don't know how. Is there a certain pattern I can always use to show that a language is not semi-decidable?

  • $\begingroup$ Hope its better now. Still learning. Thanks for your advice. $\endgroup$ – Javiator Dec 1 '15 at 19:14
  • $\begingroup$ Hint. Suppose you had such a TM, $M_{H'}$, and gave it its own description as input? See if you can come up with a contradiction. $\endgroup$ – Rick Decker Dec 1 '15 at 22:04
  • $\begingroup$ Yes, I guess I can. But is this enough to show that the problem is not semi-decidable? What do I need to show to prove a problem is not recursively enumarable? $\endgroup$ – Javiator Dec 2 '15 at 8:37
  • $\begingroup$ (a) Yes. (b) One way is to do as I suggested. Another way is to find a reduction from a known non-r.e. language. $\endgroup$ – Rick Decker Dec 3 '15 at 20:52
  • 1
    $\begingroup$ Possible duplicate of Complement of halting set is not r.e $\endgroup$ – dkaeae May 22 '19 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.