Thema6
Aus ProgrammingWiki
Aufgabe 1
Satz: Wenn P unentscheidbar ist und P ist reduzierbar auf P', so ist auch P' unentscheidbar.
Beweisen Sie den vorhergehenden 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 AVerwenden Sie im Beweis die folgenden Aussagen:
A: P' ist entscheidbar
B: P ist reduzierbar auf P'
C: P ist entscheidbar
Mit Hilfe einer Wahrheitstabelle kann der vorhergehende Satz bewiesen werden.
| A | B | C | S1 =A \wedge B | S1 \Rightarrow C | S2 =\neg C \wedge B | S2 \Rightarrow \neg A | A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A |
|---|---|---|---|---|---|---|---|
| |1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| |1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| |1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| |1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| |0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| |0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| |0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| |0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Aufgabe 2
Zeigen Sie die Unentscheidbarkeit von L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \} durch Reduktion des Halteproblems.