Opérations sous lesquelles la classe des langues indécidables n'est pas fermée

Existe-t-il des langages indécidables tels que leur union / intersection / langage concaténé est décidable? Quelle est l'interprétation physique d'un tel exemple car en général, les langages indécidables ne sont pas fermés sous ces opérations?

Que dire de la fermeture de Kleene? En avons-nous aussi des exemples? Est-ce que la fermeture d'une langue indécidable peut être décidable?

Peut-on aussi généraliser de telles classes indécidables?

Oui, soit le codage binaire du problème d'arrêt et , , puis (pourquoi?)$H$$A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$$B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$$AB=\{0,1\}^{\ast}$

Nous savons que le langage de l'arrêt est indécidable. Soit H son codage binaire. On peut également affirmer que le complément de H est indécidable. Par conséquent, l'union / l'intersection de H et HComp sont et , qui sont décidables.$\Sigma^*$$\phi$

Idem pour l'étoile Kleene (fermeture Kleene):

définir avec étant le problème d'arrêt. est clairement indécidable, et , qui est régulier (donc décidable).$\text{HP}' = \text{HP} \cup \{0,1\}$$HP$$\text{HP}'$$(\text{HP}')^* = \Sigma^*$

Ran a montré que les langues indécidables ne sont pas fermées sous l'opération de l'étoile de Kleen; mais ils ne sont pas fermés sous une simple concaténation "self" ( ); par exemple:$L \cdot L = L^2 = \{ xy \mid x,y\in L \}$

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

L $L$ est indécidable, mais est décidable.$L^2$