1
$\begingroup$

I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram.

enter image description here

However, in my assignment the TA struck out "undecidable" and wrote "not semi-decidable". Why is "undecidable" wrong if it's both not semi-decidable and not decidable?

$\endgroup$
  • 1
    $\begingroup$ You're right; the TA isn't. $\endgroup$ – Rick Decker Nov 12 '17 at 19:50
  • $\begingroup$ @RickDecker thanks! If you like, write it as an answer so that I can accept it. $\endgroup$ – Kennet Celeste Nov 12 '17 at 19:52
  • 1
    $\begingroup$ @RickDecker Huh? You don't even know what langauge the asker is talking about, so how on earth can you declare that it's not semi-decidable? $\endgroup$ – David Richerby Nov 12 '17 at 20:17
1
$\begingroup$

Undecidable isn't wrong: "undecidable" means exactly the same thing as "not decidable". However, your TA is saying that you can make the strictly stronger statement that the set is not even semi-decidable. This implies that it's undecidable, but isn't implied by "it is undecidable".

Suppose you were, instead in a biology class. You wrote "This is not a lizard" and your TA crossed it out and wrote "This is not any kind of reptile." You're both right, but your TA's version has more information in it.

$\endgroup$
  • $\begingroup$ Thanks! I now understand it ... I missed the point that "not even SD" is stronger than "undecidable" $\endgroup$ – Kennet Celeste Nov 12 '17 at 20:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.