BuK/IIm11/BuK-Übung06

Wiki-Quelltext dieser Seite.

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
Aquivalenz 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: P0 ist entscheidbar. B: P ist reduzierbar auf P0. C: P ist
entscheidbar.

== Unentscheidbarkeitsbeweis ==