Kreativaufgabe3
Gegeben: $ M_{1},M_{2} \subseteq A^{*} \text{ mit } f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} $
Gesucht:
M_{1} \cap M_{2} zweier aufzählbar unendliche Mengen M_{1},M_{2}\subseteq A^{*} ist eine aufzählbare Menge.
aufzählbare = abzählbar und berechenbar Lösung:
(1) M_{1} \cap M_{2} = \emptyset Bsp.: M_{1} = \text{ungeraden Zahlen} \\ M_{2} = \text{geraden Zahlen} \\
M_{1} \cap M_{2} = \emptyset \square(2)
Lösungsansatz: Konstruieren einer Semi-Entscheidbaren Methode die Wahr zurück gibt wenn w \in M_{1} \cap M_{2}\\ Frage: Darf man eine Semi entscheidbare Funktion anstatt einer Aufzählprozedur benutzen??? Antwort:
Wir konstruieren eine semi-entscheidbare Methode die Schritt für Schritt mithilfe der Aufzählungsfunktion f(n) ein Element aus der aufzählbaren Menge M erzeugt und mit den übergebenen w vergleicht. Dabei liefert sie wahr wenn w = f(n) und ist sonst nicht definiert.
\chi M(w)=\begin{cases} wahr, \text{ wenn } f(n) = w \text{ für alle } n \in \N \\ \perp, \text{ wenn } f(n) \neq w \text{ für alle } n \in \N \end{cases}Satz: Wenn M \subseteq \N aufzählbar ist, so ist M semi-entscheidbar.
Wie könnte die Methode aussehen??
Mithilfe der semi-entscheidbaren Funktion kann man nun überprüfen ob ein w in der Schnittmenge liegt
h(w)=\begin{cases} wahr, \text{ wenn } w = g(i) \text{ und } w = f(j) \\ \perp, \text{sonst} \end{cases}