BuK/IIm11/Studenten/sistsche/Kreativaufgabe3

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
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ählbare = abzählbar und berechenbar
Lösung:

(1) $ M_{1} \cap M_{2}  = \emptyset $
Bsp.:
$ M_{1} = \text{ungeraden Zahlen} $ \\
$ M_{2} = \text{geraden Zahlen} $ \\
$ M_{1} \cap M_{2}  = \emptyset \square $ 

(2)

Lösungsansatz: Konstruieren einer Semi-Entscheidbaren Methode die Wahr zurück gibt wenn $ w \in M_{1} \cap M_{2}$\\
Frage: Darf man eine Semi entscheidbare Funktion anstatt einer Aufzählprozedur benutzen???
Antwort: 

Wir konstruieren eine semi-entscheidbare Methode die Schritt für Schritt mithilfe der Aufzählungsfunktion $f(n)$ ein element aus der aufzählbaren Menge $M$ erzeugt und mit den übergebenen $w$ vergleicht. Dabei liefert sie $wahr$ wenn $w = f(n)$ und ist sonst nicht definiert
$$\chi M(w)=\begin{cases}
wahr, \text{ wenn } f(n) = w \text{für alle } n \in \N \\
\perp, \text{ wenn } f(n) \neq w \text{für alle } n \in \N
\end{cases}$$ 

Satz: Wenn $ M \subseteq \N$ aufzählbar ist, so ist M semi-entscheidbar.

Wie könnte die Methode aussehen??
<code id="4f797f955cc29">(define semi_decide_m
  (lambda (auffkt w)
    (letrec ((n 0)
             (semi_decide_m_helper
              (lambda  (auffkt w n)
                (if (equal? (auffkt n) w)
                    #t
                    (semi_decide_m_helper auffkt w (+ n 1))))))
      (semi_decide_m_helper auffkt w 0))))

(define auffkt-gerade 
  (lambda (n)
    (* 2 n)))
</code>
<run id="4f797f955cc93">(semi_decide_m auffkt-gerade 2)</run>

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