Operaciones bajo las cuales la clase de lenguajes indecidibles no está cerrada

¿Existen idiomas indecidibles tales que su lenguaje de unión / intersección / concatenado sea decidible? ¿Cuál es la interpretación física de tal ejemplo porque, en general, los lenguajes indecidibles no están cerrados bajo estas operaciones?

¿Qué podemos decir sobre el cierre de Kleene? ¿Tenemos ejemplos para ello también? Es decir, ¿puede ser decidible el cierre de un lenguaje indecidible?

Además, ¿podemos generalizar tales clases indecidibles?

Sí, sea codificación binaria del problema de detención y A = 0 H ∪ 1 { 0 , 1 } ∗ ∪ { ϵ } , B = 1 H ∪ 0 { 0 , 1 } ∗ ∪ { ϵ } , entonces A B = { 0 , 1 } ∗ (¿por qué?)$H$$A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$$B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$$AB=\{0,1\}^{\ast}$

Sabemos que el lenguaje vacilante es indecidible. Deje H ser su codificación binaria. También podemos afirmar que el complemento de H es indecidible. Por lo tanto, la unión / intersección de H y HComp son y ϕ , que son decidibles.$\Sigma^*$$\phi$

Lo mismo vale para la estrella de Kleene (cierre de Kleene):

establezca siendo H P el problema de detención. HP ′ es claramente indecidible, y ( HP ′ ) ∗ = Σ ∗ , que es regular (por lo tanto, decidible).$\text{HP}' = \text{HP} \cup \{0,1\}$$HP$$\text{HP}'$$(\text{HP}')^* = \Sigma^*$

$L \cdot L = L^2 = \{ xy \mid x,y\in L \}$

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

$L$$L^2$