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 | test