Skip to main content
Tweeted twitter.com/StackCompSci/status/1197439590258356224
Became Hot Network Question
edited title
Link

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

Source Link

Is the subtraction between two undecidable languages regular?

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?