0
$\begingroup$

I am taking a computer theory class and one of the exercises is to prove that the property "doesn't halt for some input" is not semidecidable. This property is the negation of the property "halts for all inputs".

I know that the halting problem is undecidable, but i need some kind of contradition to prove that the negation ("doesn't halt for some input") is not semidecidable as well.

Improve this question
$\endgroup$
6
  • $\begingroup$ Just reduce to the halting problem. Hint: consider machines which ignore thier inputs. $\endgroup$ – Andrej Bauer Jan 12 '17 at 17:56
  • $\begingroup$ Decidable means that you have a Turing Machine that takes an input $x$ and says "yes" if $x\in P$ or "no" otherwise. If you have a Turing Machine $M$ that decides $P$, you can define a new machine $M'$ that runs $M'$ and then swap "yes" and "no", and $M'$ will decide the complement of $P$. $\endgroup$ – xavierm02 Jan 12 '17 at 18:15
  • $\begingroup$ This is so standard, we probably have it already on the site. $\endgroup$ – Raphael♦ Jan 12 '17 at 18:35
  • $\begingroup$ See our reference questions on proving undecidability (some techniques are for resp. apply to proving non-semi-decidability) and reduction techniques. $\endgroup$ – Raphael♦ Jan 12 '17 at 18:37
  • $\begingroup$ @Raphael i am trying to follow those links, but the explanation isn't so clear to me. the first link has examples of how to prove that certain language isn't decidable but doesn't show how to prove that it isn't even semidecidable. $\endgroup$ – user90210 Jan 12 '17 at 21:03

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.