Vorlesung6
Übungsaufgabe 1, VL S.14
Eine TM soll überprüfen ob w die Form uu besitzt. Für u gilt a^ib^ic^i, bei Korrektheit von w soll u auf dem Band hinterlassen werden.
Übungsaufgabe 2, VL S.17
Beweisen sie mittels Aussagenlogik A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A.
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 Czu beweisen ist:
\neg C \wedge B \Rightarrow \neg ABeweis:
| A | \neg A | B | C | \neg C | A \wedge B | A \wedge B \Rightarrow C | \Leftrightarrow | B \wedge \neg C | B \wedge C \Rightarrow \neg A |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
Folgerung: Unter Beachtung von Satz 1 und deren Richtigkeit, kann man aufgrund der Äquivalenz der Wahrheitstabelle folgende Aussage treffen. Wenn P nicht entscheidbar ist und P auf P' reduziert wird dann ist P' nicht entscheidbar.
Übungsaufgabe 3, VL S.24
Zeigen sie die Unentscheidbarkeit von L_{\Sigma^{*}} := \{ \langle M \rangle | L(M) = \Sigma^{*} \} durch Reduktion des Halteproblems.
Beweisfigur:
Das Halteproblem soll hierbei auf die Unentscheidbarkeit der Entscheidbarkeit der Allsprache zurückgeführt werden. Allgemein kann man zur Veranschaulichung zur Reduzierbarkeit Beweisfiguren benutzen. Dies ist oben zu sehen. M_2 stellt die Turing-Maschine dar, welche das Halteproblem (L_H) d.h. P auf die Entscheidbarkeit der Allsprache (L_{\Sigma^{*}}) d.h. P' reduziert. M_2 bekommt als Eingabe eine Turing-Maschinen-Codierung und ein Wort und erzeugt ein Wort aus \Sigma^{*}.
Das erzeugte Wort wird der Turing-Maschine M_1 übergeben, diese entscheidet ob ein Wort w zur Allsprache gehört oder nicht. Demzufolge ist die Ergebnismenge von M_2 = \{ wahr, falsch \}.