0
$\begingroup$

I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable.

This is confusing me because if $L$ were to be a semi-decidable language, then this would be easy to prove (with either pseudocode or TMs), but as I understand not all undecidable languages are semi-decidable, and I don't know what to do with those ones.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

If $L$ is undedidable and $A$ is finite, then $L \cup A$ is undecidable. To see this notice that, given $w \in \Sigma^*$: $$w \in L \iff (w \in L \cap A) \; \vee \; (w \in L \cup A \;\wedge\; w\not\in A).$$

Since $A$ if finite both $A$ and $L \cap A$ (which is also finite) are decidable. That is, we can test whether $w \in L \cap A$ and whether $w \not\in A$. If $L \cup A$ were decidable the above formula would then imply that $L$ must also be decidable, a contradiction.

If $L$ is undedidable and $B$ is decidable, then $L \cup B$ might or might not be undecidable, depending on $B$. An example in which $L \cup B$ is undecidable is the one discussed before: let $B$ be any finite language, e.g., $B=\emptyset$. An example in which $L \cup B$ is decidable is $B=\Sigma^*$ since $L \cup B = \Sigma^*$.

$\endgroup$
0

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.