How can I show that the following language is neither semi decidable nor co-semi decidable without using Rice's Theorem?

enter image description here

Further for the following language, how would I show that it IS co-semi decidable but not decidable for |Σ| > 1

enter image description here

  • 3
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual issues but just solving homework-style exercises for you is unlikely to really help you. $\endgroup$ Jan 23 '17 at 15:04
  • $\begingroup$ The titular question is funny, because using Rice's theorem is not a reduction. ;) That said, check out our reference question! $\endgroup$
    – Raphael
    Jan 23 '17 at 20:19
  • $\begingroup$ Please ask only one question per post. These two are indeed related -- do you see the connection? $\endgroup$
    – Raphael
    Jan 23 '17 at 20:20

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.