BuK/IIm18/Vorlesung6
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Übungsaufgabe 1, VL S.14 ==
Eine TM soll überprüfen ob $w$ die Form $uu$ besitzt. Für $u$ gilt $a^ib^ic^i$, bei Korrektheit von w soll u auf dem Band hinterlassen werden.
<popup name="Springerproblem">
Das Springerproblem untersucht die Frage: "Gibt es einen Weg, bei dem der Springer jedes Feld eines n mal n großen Schachbretts genau einmal besucht?".
</popup>
== Übungsaufgabe 2, VL S.17 ==
Beweisen sie mittels Aussagenlogik $A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$.
Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:
$A: P'$ ist entscheidbar
$B: P$ ist reduzierbar auf $P'$
$C: P$ ist entscheidbar
Als gegeben kann dabei nach Satz 1 betrachtet werden dass:
$A \wedge B \Rightarrow C$
zu beweisen ist:
$\neg C \wedge B \Rightarrow \neg A$
Beweis:
<table border=1>
<tr>
<th>$A$</th>
<th>$\neg A$</th>
<th>$B$</th>
<th>$C$</th>
<th>$\neg C$</th>
<th>$A \wedge B$</th>
<th>$A \wedge B \Rightarrow C$</th>
<th>$\Leftrightarrow$</th>
<th>$B \wedge \neg C$</th>
<th>$B \wedge C \Rightarrow \neg A$</th>
</tr>
<tr>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
</tr>
<tr>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$1$</td>
<td>$1$</td>
</tr>
<tr>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
<tr>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$0$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
<td>$1$</td>
<td>$0$</td>
<td>$1$</td>
</tr>
</table>
Folgerung: Unter Beachtung von Satz 1 und deren Richtigkeit, kann man aufgrund der Äquivalenz der Wahrheitstabelle folgende Aussage treffen.
Wenn $P$ nicht entscheidbar ist und $P$ auf $P'$ reduziert wird dann ist $P'$ nicht entscheidbar.
== Übungsaufgabe 3, VL S.24 ==
Zeigen sie die Unentscheidbarkeit von $L_{\Sigma^{*}} := \{ \langle M \rangle | L(M) = \Sigma^{*} \}$ durch Reduktion des Halteproblems.
Beweisfigur:
[[Bild:S3fagawa_Beweisbild.png]]
Das Halteproblem soll hierbei auf die Unentscheidbarkeit der Entscheidbarkeit der Allsprache zurückgeführt werden.
Allgemein kann man zur Veranschaulichung zur Reduzierbarkeit Beweisfiguren benutzen.
Dies ist oben zu sehen.
$M_2$ stellt die Turing-Maschine dar, welche das Halteproblem ($L_H$) d.h. $P$ auf die Entscheidbarkeit der Allsprache ($L_{\Sigma^{*}}$) d.h. P' reduziert.
$M_2$ bekommt als Eingabe eine Turing-Maschinen-Codierung und ein Wort und erzeugt ein Wort aus $\Sigma^{*}$.
Das erzeugte Wort wird der Turing-Maschine $M_1$ übergeben, diese entscheidet ob ein Wort $w$ zur Allsprache gehört oder nicht. Demzufolge ist die Ergebnismenge von $M_2 = \{ wahr, falsch \}$.
$M_2$ liefert wahr, wenn das produzierte Wort $w$ in der Allsprache, der Menge aller Wörter über einem Alphabet, enthalten ist oder kurz: $w \in \Sigma^{*}$
Hierzu ist es notwendig das $\langle M \rangle w$ stoppt.
$M_2$ liefert falsch, wenn das Wort $w \notin \Sigma^{*}$, d.h. $\langle M \rangle w$ stoppt nicht.
Somit kann man aus der Unentscheidbarkeit des Halteproblems, die Unentscheidbarkeit der Allsprache begründen