BuK/IIm10/BuK-Übung07 G1

Wiki-Quelltext dieser Seite.

= Wort-spezifische TM =
== Aufgabenstellung ==
Geben Sie sich eine TM M  vor, die die Funktion <math>f: \mathbb{N}_0 \mapsto \mathbb{N}_0 </math> berechnet, d.h. die angesetzt auf ein Eingabewort <math>w \in \mathbb{N}_0</math> das Resultat <math>M(w</math>) auf das Band schreibt und den Kopf auf das erste Zeichen von <math>M(w)</math> setzt.

Testen Sie diese Maschine ausgiebig. Verwenden Sie AutoEdit aus AtoCC.

Entwickeln Sie anschließend für ein konkretes Wort <math>w \in \mathbb{N}_0</math> eine TM <math>M_w</math> aus <math>M</math> durch Modifikation der Definition von <math>M</math> per Hand. Wenn <math>M_w</math> auf dem (anfangs) leeren Band gestartet wird, soll <math>M_w</math> als erstes <math>w</math> auf das Band schreiben und sich anschließend verhalten, wie <math>M(w)</math>, sodass <math>M_w(\epsilon) = M(w)</math>.

Machen Sie sich klar, dass auf diese Weise jedem Wort <math>w \in \mathbb{N}_0</math> je eine spezielle TM <math>M_w</math> zugeordnet werden kann.

== Lösung ==
Die erste TM berechent die Formel <math>f(n) \mapsto n</math>, indem sie das erste Zeichen liest, es gleich wieder schreibt und nach links geht. Anschließend wird noch einmal nach rechts gegangen, damit der Lesekopf auf dem ersten Eingabezeichen steht. Danach crasht die TM.

Nachfolgend ist der dazugehörige Übergangsgraph zu sehen:

[[Datei:Aufgabe 1.png]]

Im zweiten Teil der Aufgabe, wird der ersten Maschine eine TM vorgeschaltet, die die Zahl <math>123456789</math> auf das Band schreibt.

[[Datei:Aufgabe 1 Teil 2.png]]

= Wahrheitswertetafelmethode für aussagenlogische Äquivalenzen =
== Aufgabenstellung ==
Verwenden Sie die Wahrheitswertetafelmethode, um zu zeigen, dass aus

<math>Wenn\text{ }P'\text{ }entscheidbar\text{ }und\text{ }P \leq P',\text{ }dann\text{ }P\text{ }entscheidbar.
</math>

folgt

<math>Wenn\text{ }P\text{ }unentscheidbar\text{ }und\text{ }P \leq P',\text{ }dann\text{ }P'\text{ }unentscheidbar.</math>

== Lösung ==
Wenn man die folgende Wahrheitstabelle aufstellt sieht man, dass die beiden rot markierten Spalten gleich sind. In der ersten Spalte sieht man das was gilt und in der zweiten das zu Zeigende.

<math>
\begin{array}{ccc}
A & = & P' \text{ } entscheidbar\\
B & = & P \leq P'\\
C & = & P \text{ } entscheidbar
\end{array}
</math>

[[Datei:Wahrheitstabelle Aufgabe2.png]]

= Reduktion =
== Aufgabenstellung ==
Zeigen Sie durch Reduktion des Halteproblems, dass <math>L_{\Sigma^*} = \{\left\langle M \right\rangle | L(M) = \Sigma^* \}</math> unentscheidbar.

== Lösung ==
Es ist zu Zeigen, dass eine TM, die alle Wörter akzeptiert, nicht existiert.

Dazu wird dieses Problem auf das Halteproblem zurück geführt und es wird angenommen, dass eine solche TM existiert.

Um das zu beweisen, müssen zwei TM nacheinander geschaltet werden. Die erste berechnet die Funktion f. Das bedeutet, dass sie aus <math>M(w)</math> die Ausgabe <math>\left\langle M' \right\rangle /math> erzeugt. Die Ausgabe wird dann in die zweite TM eingegeben, die die Funktion <math>L_{\Sigma^*}</math> berechnet. Zusammen ergeben diese beiden TM eine TM, die das Halteproblem berechnet (<math>M_H</math>).

* 1, wenn <math>M(w)</math> stoppt, gdw. <math>M'(\epsilon)</math> stoppt und <math>M_H</math> stoppt.
* 0, wenn <math>M(w)</math> nicht stoppt, gdw. <math>M'(\epsilon)</math> stoppt und <math>M_H</math> stoppt.

Damit ist ein Widerspruch erzeugt.