BuK-KA-Durchschnittsmenge
Aufgabenstellung
Weisen Sie nach, dass die Durchschittsmenge (Schnittmenge) zweier aufzählbarer Mengen M_{1},M_{2} \subseteq A^{*} eine aufzählbare Menge ist. Implementieren Sie eine zugehörige Aufzählfunktion.
Satz
Die Durchschnittsmenge M_{1} \cap M_{2} zweier aufzählbarer Mengen M_{1},M_{2} \subseteq A^{*} ist eine aufzählbare Menge.
Beweis
Gegeben sind die Aufzählprozeduren für die surjektiven Funktionen f: \N \rightarrow M_{1} \text{ und } g: \N \rightarrow M_{2} . Gesucht ist eine Aufzählfunktion h: \N \rightarrow M_{1} \cap M_{2} mit
h(i)=\begin{cases} f(i), \text{ wenn } \chi_{M_{1} \cap M_{2}}(f(i))\\ h(i+1), \text{ sonst}\\ \end{cases}Die Schnittmenge M_{1} \cap M_{2} ist aufzählbar, wenn h berechenbar ist. f(i) ist für alle i \in \N berechenbar, da M_{1} eine aufzählbare Menge ist. Außerdem ist \chi_{M_{1} \cap M_{2}}(w), w \in A^{*} mit
\chi_{M_{1} \cap M_{2}}(w)=\begin{cases} wahr, \text{ wenn } \chi_{M_{1}}(w) \wedge \chi_{M_{2}}(w)\\ \perp, \text{ sonst}\\ \end{cases}berechenbar, da die partiellen semi-chrakteristischen Funktionen \chi_{M_{1}} und \chi_{M_{2}} berechenbar sind. \square
Gesucht:
M_{1} \cap M_{2} zweier aufzählbar unendliche Mengen M_{1},M_{2}\subseteq A^{*} ist eine aufzählbare Menge.
aufzählbar = abzählbare und berechenbare Lösung:
(1) M_{1} \cap M_{2} = \emptyset
Beispiel.:
M_{1} = \text{ungeraden Zahlen} M_{2} = \text{geraden Zahlen} M_{1} \cap M_{2} = \emptyset \square(2)
Lösungsansatz: Konstruieren einer Methode, die alle Elemente der Schnittmenge geordnet liefert.Dazu notwendig ist eine semi-entscheidbare Funktion, die w als Ergebnis liefert, wenn w \in M_{1} \cap M_{2}, , wobei w = f(i) = g(j).
Wir konstruieren eine semi-entscheidbare Methode, die Schritt für Schritt mithilfe der Aufzählungsfunktionen f(n) und g(n), n \in \N eine Teilmenge aus den aufzählbaren Mengen M_{1} bzw. M_{2} erzeugt. Anschließend kann überprüft werden, ob w in diesen (endlichen) Teilmengen vorhanden ist oder nicht.
\chi M(w)=\begin{cases} wahr, \text{ wenn } f(i) = g(j) = w \text{ für alle } i,j \in \N\\ \perp, \text{ wenn } f(i) \neq g(j) \neq w \text{ für alle } i,j \in \N\\ \end{cases}Aus der Tatsache, dass die Schnittmenge zweier Mengen höchstens die Vereinigung der beiden Mengen darstellt, folgt der Schluss, dass die Schnittmenge selbst auch abzählbar ist. Die Teilmenge einer abzählbaren (unendlichen) Menge ist höchstens abzählbar (unendlich).
Die Berechnung der Schnittmenge und der damit verbundene Nachweis der Berechenbarkeit zweier aufzählbarer Mengen wird mittels Turing-Maschinen realisiert. Benötigt wird folglich eine Funktion, die ein Ergebnis liefert, wenn w \in M_{1} und w \in M_{2}. Die jeweilige Überprüfung, ob das Wort zur gegebenen Menge M_{1} gehört, kann mittels Funktion realisiert werden, da in der Behauptung die Aufzählbarkeit gegeben ist. Es existiert also eine semi-entscheidbare Funktion, welche die Existenz von w in M_{1} bestätigt (oder nicht endet). Gleiches gilt auch für M_{2}. Die Akzeptanz, ob w \in M_{1} bzw. w \in M_{2} kann mittels einer Turing-Maschine realisiert werden.
Wie bereits in der Lehrveranstaltung formale Sprachen und abstrakte Automaten erläutert wurde, ist eine Turing-Maschine in der Lage, das Verhalten anderer Turing-Maschinen zu simulieren. Wir können folglich durch die Verwendung der bereits existenten Turing-Maschinen bestimmen, ob das Wort zu beiden Menge gehört.
In der uten abgebildeten Scheme-Prozedur werden die ersten n Elemente der Schnittmenge als Resultat geliefert. Um gewährleisten zu können, dass die Funktion nach endlich vielen Schritten entscheidet, ob ein Wort w auch in der anderen (Teil-) Menge vorhanden ist, werden die von den Turing-Maschinen akzeptierten Mengen an Wörtern schrittweise und abwechselnd erweitert. Durch die Schaffung der endlichen Teilmengen kann zumindest in den Zwischenschritten das Terminieren nach n = |M| Schritten gewährleistet werden.