BuK-Übung06

Vorlesungsfolien

Aufgaben werden am 08.05. um 23:00 übertragen

Reduzierbarkeit

Aufgabe 1 (Max Wielsch, Raik Bienik)

(Aufgabe siehe: VL Slide 14)

Konstruieren sie eine Prozedur, welche prüft ob w die Form uu besitzt!

Aufgabe 2 (Stefan Lüttke, Felix Nitsche)

(Aufgabe siehe: VL Slide 15/16)

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.

Unentscheidbarkeitsbeweis

Aufgabe 1 (Ingo Körner, Christoph Ochmann)

(Aufgabe siehe: VL Slide 13)

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