Is it possible that the subtraction between two undecidable languages is regular?

Question

If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set?

What's a good way of tackling this question? Me and some classmates have been stuck on this question for a while, and this was the best we've got:

It should be possible given the following example:

Let $L_1=H\cup a^*$ and $L_2=H$, where $H=\{<M,w>:$ Turing machine $M$ halts on $w$$\}$, so $L_1-L_2=L_1\cap \lnot L_2=(H\cup a^*)\cap \lnot H=\lnot H\cap a^* = a^*$ which is regular. (we are saying $H$ does not contain $a^*$, so $\lnot H$ must contain $a^*$, hence why the intersection gives $a^*$.)

But we are not confident this is correct due to the last part with the intersection does not feel right. What's the answer to this question?

Answer 1

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.

Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L_1 = L_2 \cup \lbrace a \rbrace.$$ Now it is obvious that $a \not\in L_2$ because all words in $L_2$ start with $b$. Also, $L_2$ and $L_1$ are undecidable because there are easy reductions from $H$ to them, and back. And of course we have $$L_1 \setminus L_2 = \{a\},$$ which is decidable. You can make the example more complicated by taking any decidable langauge $D$ and define $L_2$ as before, but change $L_1$ to $$L_1 = L_2 \cup \{a w \mid w \in D\}.$$ This way $L_1 \setminus L_2$ is computably isomorphic to $D$.

• Pengibaby: Thank you so much for the reply and your detailed explaination! :)

Answer 2

Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.

• Pengibaby: Thank you for your help! I really appreciate it :)
• J.-E. Pin: You're welcome.

Answer 3

As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$.

The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$.

Here is the simplest way to find $L_2$ so that $L_1-L_2$ is undecidable, given any undecidable language $L_1$. Since $L_1$ is undecidable, it must contain at least one word. Let $w\in L_1$. Let $L_2$ be $L_1$ without $w$. Then $L_1-L_2=\{w\}$ is regular. You can check that $L_2$ is undecidable.

---

Exercise 1. (easy) Given an undecidable language $L_2$, find an undecidable language $L_1$ such that $L_1-L_2$ is regular.

Exercise 2. (easy) Give an example where the subtraction between two non-context-free languages is regular.

Exercise 3. (one or several minutes) Give any regular language $R$, find an example such that the subtraction between two undecidable languages is $R$.

• Pengibaby: Thank you for your response and clearing things up :)