Operationen, bei denen die Klasse der unentscheidbaren Sprachen nicht geschlossen ist

Gibt es unentscheidbare Sprachen, deren Vereinigung / Schnittmenge / verkettete Sprache entscheidbar ist? Was ist die physikalische Interpretation eines solchen Beispiels, da im Allgemeinen nicht entscheidbare Sprachen unter diesen Operationen nicht geschlossen werden?

Was können wir über die Schließung von Kleene sagen? Haben wir auch Beispiele dafür? Dh kann der Abschluss einer unentscheidbaren Sprache entscheidbar sein?

Können wir solche unentscheidbaren Klassen auch verallgemeinern?

Ja, sei eine binäre Codierung des Halteproblems und , , dann (warum?)$H$$A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$$B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$$AB=\{0,1\}^{\ast}$

Wir wissen, dass die haltende Sprache nicht zu entscheiden ist. Sei H seine binäre Kodierung. Wir können auch sagen, dass das Komplement von H unentscheidbar ist. Daher sind Vereinigung / Schnittmenge von H und HComp und , die entscheidbar sind.$\Sigma^*$$\phi$

Gleiches gilt für den Kleene-Stern (Kleene-Verschluss):

setze wobei das Stopp-Problem ist. ist eindeutig unentscheidbar, und , was regulär ist (also entscheidbar).$\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$