BuK/IIm11/Studenten/sistsche/Kreativaufgabe3

Wiki-Quelltext dieser Seite.

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