12
$\begingroup$

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?

$\endgroup$
21
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy