Thema6

Aus ProgrammingWiki

Aufgabe 1

Satz: Wenn P unentscheidbar ist und P ist reduzierbar auf P', so ist auch P' unentscheidbar.

Beweisen Sie den vorhergehenden 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

Mit Hilfe einer Wahrheitstabelle kann der vorhergehende Satz bewiesen werden.

$A$	$B$	$C$	$S1 =A \wedge B$	$S1 \Rightarrow C$	$S2 =\neg C \wedge B$	$ S2 \Rightarrow \neg A$	$A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$
$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$0$$	$$1$$	$$1$$
$$1$$	$$1$$	$$0$$	$$1$$	$$0$$	$$1$$	$$0$$	$$1$$
$$1$$	$$0$$	$$1$$	$$0$$	$$1$$	$$0$$	$$1$$	$$1$$
$$1$$	$$0$$	$$0$$	$$0$$	$$1$$	$$0$$	$$1$$	$$1$$
$$0$$	$$1$$	$$1$$	$$0$$	$$1$$	$$0$$	$$1$$	$$1$$
$$0$$	$$1$$	$$0$$	$$0$$	$$1$$	$$1$$	$$1$$	$$1$$
$$0$$	$$0$$	$$1$$	$$0$$	$$1$$	$$0$$	$$1$$	$$1$$
$$0$$	$$0$$	$$0$$	$$0$$	$$1$$	$$0$$	$$1$$	$$1$$

Aufgabe 2

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