BuK/IIm11/BuK-Übung06

Wiki-Quelltext dieser Seite.

[http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeitstheorie/VL/vl06.pdf 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 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: $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.