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$
1
  • $\begingroup$ You can always edit your question so that it appears nice when future readers read it the first time. I just did it on behalf of you this time. (This comment will be deleted soon.) $\endgroup$ – John L. Jan 8 at 23:38
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, privacy policy and cookie policy

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