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

$\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.

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

$\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.

$\endgroup$

Your Answer

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