# Operations under which the class of undecidable languages isn't closed

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable languages are not closed under these operations?

What can we say about the kleene closure? Do we have examples for it too? I.e. can the closure of an undecidable language be decidable?

Also, can we generalize such undecidable classes?

## 4 Answers

Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$, $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$, then $AB=\{0,1\}^{\ast}$ (why?)

We know that the halting language is undecidable. Let H be its binary encoding. We can also state that complement of H is undecidable. Therefore, union/intersection of H and HComp are $\Sigma^*$ and $\phi$, which are decidable.

Same holds for the Kleene star (Kleene closure):

set $\text{HP}' = \text{HP} \cup \{0,1\}$ with $HP$ being the halting problem. $\text{HP}'$ is clearly undecidable, and $(\text{HP}')^* = \Sigma^*$, which is regular (thus decidable).

Ran showed that undecidable languages are not closed under the Kleen star operation; but they aren't closed under a simple "self" concatenation ($L \cdot L = L^2 = \{ xy \mid x,y\in L \}$) either; for example:

$L = \{1\} \cup \{2n\} \cup \{ 2n+1 \mid n \in Halt \}$

$L$ is undecidable, but $L^2$ is decidable.