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ä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 } n,i,j \in \N, i,j <= n\\ \perp, \text{ wenn } f(n) \neq g(j) \neq w \text{ für alle } n,i,j \in \N, i,j <= n\\ \end{cases}Satz: Wenn M \subseteq \N aufzählbar ist, so ist M semi-entscheidbar.
Fragestellung: Wie könnte die Methode aussehen?
Mithilfe der semi-entscheidbaren Funktion kann man nun überprüfen, ob 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}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 A 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 Turining-Maschinen bestimmen, ob das Wort zu beiden Menge gehört oder nicht.
In der oben 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.
Das Problem der Semi-Entscheidbarkeit besteht jedoch weiterhin, da nicht garantiert werden kann, ob ein n-tes Element existiert und die Funktion nach endlicher Zeit das gewünschte Ergebnis liefern kann (oder eben nicht).
Frage: Darf man eine semi-entscheidbare Funktion anstatt einer Aufzählprozedur benutzen?
Antwort: Semi-entscheidbare Funktion ist aufzählbar: