BuK/IIm11/Studenten/sistsche/Kreativaufgabe3

Wiki-Quelltext dieser Seite.

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.

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}$$