Wort-spezifische TM

Aufgabenstellung

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

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

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

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

Lösung

Die erste TM berechent die Formel f(n) \mapsto n, 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:

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

Wahrheitswertetafelmethode für aussagenlogische Äquivalenzen

Aufgabenstellung

Verwenden Sie die Wahrheitswertetafelmethode, um zu zeigen, dass aus

folgt

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.

Reduktion

Aufgabenstellung

Zeigen Sie durch Reduktion des Halteproblems, dass L_{\Sigma^*} = \{\left\langle M \right\rangle | L(M) = \Sigma^* \} 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 M(w) die Ausgabe \left\langle M' \right\rangle /math> erzeugt. Die Ausgabe wird dann in die zweite TM eingegeben, die die Funktion <math>L_{\Sigma^*} berechnet. Zusammen ergeben diese beiden TM eine TM, die das Halteproblem berechnet (M_H).

• 1, wenn M(w) stoppt, gdw. M'(\epsilon) stoppt und M_H stoppt.
• 0, wenn M(w) nicht stoppt, gdw. M'(\epsilon) stoppt und M_H stoppt.

Damit ist ein Widerspruch erzeugt.