Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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^*$.
