0
$\begingroup$

Reference from here If a Language is Non-Recognizable then what about its complement? There exist complementary languages of unrecognizable languages that are recognizable, and there exist complementary languages of unrecognizable languages that are undecidable.

If a language is unrecognizable, then it must be undecidable.

If a language is undecidable, then its complementary language must also be undecidable?

$\endgroup$

1 Answer 1

1
$\begingroup$

If $A(x)$ is an algorithm deciding $x\in L^c$, then $\lnot A(x)$ is an algorithm deciding $x\in L$.

To be more pedantic, by $\lnot A(x)$ I mean the algorithm that executes $A(x)$ and if that accepts (resp. rejects) then it rejects (resp. accepts). In a programming language it's likely something like bool not_a(string x) { return not a(x); }.

Hence, if $L^c$ is decidable then $L$ is such.

Using a similar argument you can prove that $L^c$ is decidable if and only if $L$ is such.

$\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.