Operacje, w których klasa nierozstrzygalnych języków nie jest zamknięta

Czy istnieją nierozstrzygalne języki, tak że ich związek / język przecięcia / konkatenacji jest rozstrzygalny? Jaka jest fizyczna interpretacja takiego przykładu, ponieważ ogólnie nierozstrzygalne języki nie są zamknięte w ramach tych operacji?

Co możemy powiedzieć o zamknięciu kleene? Czy mamy też na to przykłady? Czy to znaczy, że zamknięcie nierozstrzygalnego języka może być rozstrzygalne?

Czy możemy również uogólnić takie nierozstrzygalne klasy?

Tak, niech $H$ będzie binarnym kodowaniem problemu zatrzymania, a $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$ , $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$ , a następnie $AB=\{0,1\}^{\ast}$ (dlaczego?)

Wiemy, że język zatrzymania jest nierozstrzygalny. Niech H będzie jego kodowaniem binarnym. Możemy również stwierdzić, że uzupełnienie H jest nierozstrzygalne. Dlatego połączenie / przecięcie H i HComp to i , które są rozstrzygalne.$\Sigma^*$$\phi$

To samo dotyczy gwiazdy Kleene (zamknięcie Kleene):

set z stanowiącym problem zatrzymania. jest wyraźnie nierozstrzygalny, a , który jest regularny (a zatem rozstrzygalny).H P HP ′ ( HP ′ ) ∗ = Σ $\text{HP}' = \text{HP} \cup \{0,1\}$$HP$$\text{HP}'$$(\text{HP}')^* = \Sigma^*$

Ran pokazał, że nierozstrzygalne języki nie są zamknięte w ramach operacji gwiazdy Kleen; ale nie są one zamknięte w ramach prostej „własnej” konkatenacji ( ); na przykład:$L \cdot L = L^2 = \{ xy \mid x,y\in L \}$

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

L $L$ jest nierozstrzygalny, ale jest rozstrzygalny.$L^2$