# Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?

I was studying Turing languages for an exam and I came up with this problem for wich I haven't found a solution online. This is my question:

Let's say we have $$L_1, L_2 \subseteq\{0,1\}^*$$. $$L_1$$ is Turing-recognisable and $$L_2$$ is Turing-decidable.

Is $$L_u = L_1 \cup L_2$$ decidable? Is it recognisable?

My guess is that $$L_u$$ is just recognisable. Here is my attemp on proving it.

A language $$L \subseteq \{0,1\}^*$$ is decidable if and only if both $$L$$ and $$L^c$$ are recognisable (where $$L^c = \{0,1\}^* \setminus L$$). My idea was to prove that $$L_u$$ is recognisable and $$L_u^c$$ is not.

In our case $$L_u$$ is recognisable (trivial) and $$L_u^c = (L_1 \cup L_2)^c = (L_1^c \cap L_2^c)$$. We know that $$L_1^c$$ is recognisable and $$L_2^c$$ is not-recognisable (or else, $$L_2$$ would have been decidable). At this point I got stuck. I'm pretty sure that $$L_u^c$$ is not-recognisable, but I found this example:

Let $$L_x = \{stuff\} \cup L_1$$ be a not-recognisable language and $$L_1$$ the language we defined above. The intersection $$L_x \cap L_1 = L_1$$ wich by definition is recognisable.

Can we sometimes recognise the intersection between a not-recognisable language and a recognisable one? In other words, is my proof wrong somehow?

– D.W.
Jun 18 at 17:04

The answer to the question "Is $$L_u = L_1 \cup L_2$$ decidable?" is "sometimes".

For a positive example, let both $$L_1$$ and $$L_2$$ be the empty language.
For a negative example, let $$L_1$$ be Turing-recognisable but not Turing-co-recognisable such as the language of halting Turing machines, and let $$L_2$$ be the empty language.

The answer to the question "Is $$L_u = L_1 \cup L_2$$ Turing-recognisable?" is "Yes". In fact, we have a stronger statement below.

Proposition: the union of two Turing-recognisable languages are Turing-recognisable.
Proof: Suppose $$L_1$$ and $$L_2$$ are recognised by Turing machine $$T_1$$ and $$T_2$$ respectively. Let $$T_3$$ be the Turing machine that upon input $$s$$ simulates $$T_1$$ and $$T_2$$ simultaneously. If and only if either $$T_1$$ or $$T_2$$ accepts, $$T_3$$ accepts. Then $$T_3$$ accepts the union of $$L_1$$ and $$L_2$$.

The answer to "Can we sometimes recognise the intersection between a not-recognisable language and a recognisable one?" is "yes".

For example, let the recognisable one be the empty language.

• Thanks for the answer. I edited my question to make more clear my point. Basically if $L_u$ is "sometimes" decidable, is it always recognisable? Jun 18 at 17:03
• Yes. In fact, Turing-recognisability are closed under both union and intersection. So is decidability. Jun 18 at 17:30

A few things,

• It's hard to find what your proof attempt is trying to do. I know you're stuck, but you should at least have a strategy of what you want to do. In your proof, a good idea is to use AFSOC and look for a contradiction.
• The online theorem you found makes no sense, if we have $$L_x = S \cup L_1$$ but we don't know anything about $$L_1$$, I'm not sure why there is a claim about recognizability.

So we want to know if $$L_1 \cup L_2$$ is decidable, right? Intuitively, this is probably not true, because if $$L_1$$ is just recognizable, adding a decidable language to it should probably not in general make it decidable all of a sudden (it can though, but remember if we have no assumptions about $$L_1, L_2$$, then this has to hold in all cases).

So normally when we have an intuition that something doesn't work, we use contradiction or a counterexample.

You can have 2 options here, so you can either

1. AFSOC $$L_u = L_1 \cup L_2$$ is decidable, and try to show a contradiction, most likely that $$L_1$$ is decidable.
2. Find a counterexample

I think 2 is much easier to find. You can just take any recognizable (but not decidable) language $$L_1$$, and then take a trivial subset that is decidable, let's say a single element, to make $$L_2$$. Then $$L_2$$ is decidable, but $$L_1 \cup L_2 = L_1$$ which is not decidable. (note that we can take some element, because if $$L_1$$ is empty, then it cannot be undecidable).

• You're right, I'm gonna edit my question to make my strategy more clear. About my "online theorem", $L_1$ is the language I already defined (recognisable). I'll make this more clear aswell. Also, is my "proof" wrong? Can we prove that $L_u$ is recognisable? Jun 18 at 16:57
• Proving recognisability is trivial, because we know $L_u = L_1 \cup L_2$, and $L_1, L_2$ are both recognisable. So we can easily build a TM $T_u$ defined as $T_u \, : \, \text{Run } T_1 \text{ and } T_2 \text{ and return either if they accept}$. Notice that this $T_u$ defined is not necessarily decidable, since we don't know if $T_1$ terminates. Jun 18 at 17:27