Thema6

Aufgabe 1

Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:

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.