Kreativaufgabe3
Aus ProgrammingWiki
Archivierte Version vom 2012-04-01T15:13:24+00:00. Aktuelle Version
Gegeben: M_{1},M_{2} \subseteq A^{*} 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.
Lösung:
Konstruieren einer Methode die Wahr zurück gibt wenn w \in M_{1} \cap M_{2}
Wie sieht diese Methode aus???
Es wird ein "Pools" für die Menge M_{1} angelegt und überprüft ob das Ergebnis für g(n), welches die Menge M_{2} beschreibt, in M_{1} vorhanden ist. Somit kann man eine Turingmaschine beschreiben die hält falls der Sachverhalt eintritt jedoch nicht hält fals das wort nicht enthalten ist.
h(n)=\begin{cases} wahr, \text{ wenn } g(n) \in M_{1} \perp, \text{sonst} \end{cases}