BuK-Übung06
Aus ProgrammingWiki
Aufgaben werden am 08.05. um 23:00 übertragen
Inhaltsverzeichnis |
Reduzierbarkeit
Aufgabe 1 (Max Wielsch, Raik Bienik)
(Aufgabe siehe: VL Slide 14)
Konstruieren sie eine Prozedur, welche prüft ob $w$ die Form $uu$ besitzt!
Aufgabe 2 (Stefan Lüttke, Felix Nitsche)
(Aufgabe siehe: VL Slide 15/16)
Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:
$A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$
Verwenden Sie im Beweis die folgenden Aussagen:
A: $P'$ ist entscheidbar. B: $P$ ist reduzierbar auf $P'$. C: $P$ ist entscheidbar.
Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:
$A: P'$ ist entscheidbar
$B: P$ ist reduzierbar auf $P'$
$C: P$ ist entscheidbar
Als gegeben kann dabei nach Satz 1 betrachtet werden dass:
$A \wedge B \Rightarrow C$
zu beweisen ist:
$\neg C \wedge B \Rightarrow \neg A$
Beweis:
| $Zeile$ | $A$ | $B$ | $C$ | $E=A \wedge B$ | $F=E\Rightarrow C$ | $G=\neg C \wedge B$ | $H = G \Rightarrow \neg A$ | $I = F \Leftrightarrow H$ | $Kommentar$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | gegeben durch Satz 1 |
| 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | falsch nach Satz 1 |
| 3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 4 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | ... |
| 5 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 6 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | Einzig verbleibende Möglichkeit für $\neg C \wedge B$ |
| 7 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 8 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | ... |
In Zeile 6 befindet sich die einzig verbleibende Möglichkeit für $\neg C \wedge B$. Daraus kann abgelesen werden dass in dem Fall $\neg A$ gilt, womit Satz 2 bewiesen ist.
Unentscheidbarkeitsbeweis
Aufgabe 1 (Ingo Körner, Christoph Ochmann)
(Aufgabe siehe: VL Slide 13)
Zeigen Sie die Unentscheidbarkeit (Semi-Entscheidbarkeit) von $L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \}$ durch Reduktion der Sprache $L_{\Sigma^{*}}$ auf das Halteproblem.
Schreibe für alle Eingabewörter aus $\Sigma^{*}$ die Kodierung der Maschine M, d.h. <M>, sowie w $\in$ $\Sigma^{*}$ auf das Band einer Maschine $M_2$. Die Maschine $M_2$ ist so konstruiert, dass sie aus ihrer Eingabe <M> und w die Kodierung einer Maschine M', d.h. <M'>, zusammen mit einem Eingabewort y auf ihr Band als Ausgabe schreibt. Die Besonderheit von M' ist, dass diese Maschine mit dem Eingabewort y stoppt, wenn M(w) stoppen würde. Dabei ist y nur ein Platzhalter, denn y hat auf die Terminierung von M' keinen Einfluss. Als nächstes wird <M'> und y auf das Band einer UTM $M_1$ geschrieben. $M_1$ führt die Kodierung der Maschine M' mit dem Wort y aus. Dabei verwirft die Maschine M' als erstes ihr Eingabewort y, so dass ihr Band leer ist. Wenn die durch $M_1$ ausgeführte Maschine M' mit ihrem leeren Band hält, so heißt das, dass auch die Maschine M mit dem Wort w akzeptieren würde. Wenn die durch die Maschine $M_1$ ausgeführte Maschine M' auf dem anfangs leeren Band nicht in einem Endzustand hält, dann stoppt auch die Maschine M mit dem Wort w nicht in einem Endzustand. <M> ist $\in$ $L_{\Sigma^{*}}$ genau dann, wenn M' termiert.
