0
$\begingroup$

I tried to prove by contradiction.

$L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$ $$L_{2}=\emptyset$$ then, $$\overline L_{1}={HALT_{TM}}=\big\{ \langle M, w \rangle \mid M\text{ is TM and }M\text{ halts on input }w \big\}$$ $$\overline L_{2}=\Sigma^{*}$$ The intersection, $\overline{L_{1}}\cap \overline{L_{2}}$ is $\overline L_{1}={HALT_{TM}}$ is decidable and this is the contradiction.

Is it true?

Thanks.

$\endgroup$
2
$\begingroup$

Unfortunately your proof is not correct. The claim you want to prove or disprove is:

The union of any undecidable language and any finite language is undecidable.

To do a proof by contradiction, you need to take the opposite:

The union of some undecidable language and some finite language is decidable.

Note that the "any" (universal quantifier) turns into "some" (existential quantifier) when you apply the negation.

You showed that a contradiction follows from:

The union of any undecidable language and any finite language is decidable.

But unfortunately, that only proves:

The union of some undecidable language and some finite language is undecidable.

In other words, you can't just pick specific languages and show that their union is decidable: you need to show that your proof will work for any arbitrary $L_1$ and $L_2$ fitting the requirements.

I would suggest that you instead start with an arbitrary undecidable $L_1$ and finite $L_2$ and, from there, show that $L_1 \cup L_2$ is undecidable. Here's a hint to get you started: is $L_1 \setminus L_2$ decidable or not?

$\endgroup$
  • $\begingroup$ All right, I look at an arbitrary undecidable $L_{1}$ and finite $L_{2}$, $L_1 \setminus L_2$ isn't decidable because then I can use the language $L_{2}$ for any undecidable languages, just subtract $L_{2}$ from, to decide the language. So, it's the same about the union of them? Thanks. $\endgroup$ – Asaf Jul 28 '18 at 13:25
  • $\begingroup$ if I take some undecidable language $L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$ and some finite language $L_{2} = \emptyset$, then their union is $L_{1}$ that is undecidable. $\endgroup$ – Asaf Jul 28 '18 at 14:19
  • $\begingroup$ @Asaf Close, but you're mixing up "some" and "any" again. Your example shows that for some languages $L_1 \setminus L_2$ is undecidable, but you haven't proven that for all. (You're on the right track though!) $\endgroup$ – Draconis Jul 28 '18 at 17:07
  • $\begingroup$ I used it by the contradiction that you wrote: The union of some undecidable language and some finite language is decidable. If the contradiction is true, I can take some undecidable language $L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$ and and some finite language $L_{2} = \emptyset$, their union must be decidable. Their union is undecidable, and that is the contradiction. $\endgroup$ – Asaf Jul 28 '18 at 17:23
  • $\begingroup$ @Asaf Ah, but you're going in the wrong direction. You need to start with "the union of some undecidable language and some finite language is decidable" and go forward from that to get a contradiction. Basically, assume you have some undecidable $L_1$ and some finite $L_2$ such that $L_1 \cup L_2$ is decidable, and go from there. You can't assume anything else about the two languages. You can't set them to specific values, in particular. $\endgroup$ – Draconis Jul 28 '18 at 17:26
0
$\begingroup$

I start with $L_{1} \cup L_{2}$ is decidable.

Decidable languages are closed under difference. So, $(L_{1} \cup L_{2}) \setminus L_{2}$ must be decidable.

$(L_{1} \cup L_{2}) \setminus L_{2}= L_{1}$ but $L_{1}$ is undecidable.

$\endgroup$

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.