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$

3 Answers 3

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$
6
  • $\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
    Commented Jul 28, 2018 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
    Commented Jul 28, 2018 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
    Commented Jul 28, 2018 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
    Commented Jul 28, 2018 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
    Commented Jul 28, 2018 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$
1
  • $\begingroup$ This is true only if $L_1$ and $L_2$ are non-overlapping. $\endgroup$
    – Pontus
    Commented Feb 13, 2020 at 22:48
0
$\begingroup$

By contradiction. Suppose that for all $L_1$ undecidable and $L_2$ finite $\overline{L_1} \cap \overline{L_2}$ is decidable. Pick $L_1$ any undecidable language. The language $L_2 = \varnothing$ is certainly finite, it's complement is $\overline{L_2} = \Sigma^*$, so that $\overline{L_1} \cap \overline{L_2} = \overline{L_1}$, and that one isn't decidable if $L_1$ isn't.

$\endgroup$
1
  • $\begingroup$ What about other finite $L_2$? $\endgroup$
    – Pontus
    Commented Feb 13, 2020 at 22:50

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.