0
$\begingroup$

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.

Follow up question:

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

$\endgroup$
1
  • 1
    $\begingroup$ Please ask only one question per post. Thank you! $\endgroup$
    – D.W.
    Jun 18 at 17:04

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Pietro
    Jun 18 at 17:03
  • $\begingroup$ Yes. In fact, Turing-recognisability are closed under both union and intersection. So is decidability. $\endgroup$
    – John L.
    Jun 18 at 17:30
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Pietro
    Jun 18 at 16:57
  • $\begingroup$ 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. $\endgroup$
    – mikinty
    Jun 18 at 17:27

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.