0
$\begingroup$

This question already has an answer here:

I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper approach for this question or am I completely off mark?

I also have few other questions, give an example of a language where: 1) L ∈ D and ¬L ∈ SD − D? 2) L, ¬L ∈ SD − D?

For 1) I know D is closed under complement therefore ¬L must be decidable iff L is decidable. So there are no examples?

For 2) I know if both L and ¬L are SD, then L must be decidable. So there are also no examples?

Sorry for some these questions, I am 90% sure I am right but I'm learning everything by myself so I have no one to ask to be sure. Thanks for any help.

$\endgroup$

marked as duplicate by Raphael Jan 11 '18 at 23:38

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$ Please ask only one question per post. $\endgroup$ – Raphael Jan 11 '18 at 23:37
  • $\begingroup$ For the first one, just prove that your idea is right. Your reasoning is also right for 1) and 2) -- it seems they're trick questions. $\endgroup$ – David Richerby Jan 12 '18 at 0:26