BuK/IIm12/Studenten/siclsche/Thema6

Wiki-Quelltext dieser Seite.

==Aufgabe 1 ==

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

== Aufgabe 2 == 

Zeigen Sie die Unentscheidbarkeit von $L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \}$ durch Reduktion des Halteproblems.