Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable?

  • $\begingroup$ Isn't this a basic result whose proof can be found in any computability book? $\endgroup$ – chi Feb 7 '18 at 8:51
  • $\begingroup$ The answer depends on the exact definitions you use, but given the definitions, should be straightforward. $\endgroup$ – Yuval Filmus Feb 7 '18 at 9:05
  • $\begingroup$ Given a decider that your programs can call, could you write the other two programs that would demonstrate the semi-decidability of those two problems? How? $\endgroup$ – Davislor Feb 8 '18 at 1:58

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.