0
$\begingroup$

A decidable language must be recognizable.

Unrecognizable languages must be undecidable?

I want to know more about the relation of undecidability and unrecognizability

$\endgroup$

1 Answer 1

1
$\begingroup$

One of the most applicable basic laws of basic logic is the law of contraposition: $(P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P)$.

Therefore, if you know decidable languages must be recognizable, its contrapositive readily follows: languages that are not recognizable can not be decidable.

For a more direct reasoning, observe that a decider for a language is always also a valid recognizer for a language. Therefore if a language has a decider, it also has a recognizer and therefore is recognizable; and if it has no recognizer, it cannot have a decider either.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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