Aus ProgrammingWiki

Inhaltsverzeichnis 1 Wort-spezifische TM 1.1 Aufgabenstellung 1.2 Lösung 2 Wahrheitswertetafelmethode für aussagenlogische Äquivalenzen 2.1 Aufgabenstellung 2.2 Lösung 3 Reduktion 3.1 Aufgabenstellung 3.2 Lösung

Wort-spezifische TM

Aufgabenstellung

Geben Sie sich eine TM M vor, die die Funktion berechnet, d.h. die angesetzt auf ein Eingabewort das Resultat ) auf das Band schreibt und den Kopf auf das erste Zeichen von setzt.

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

Entwickeln Sie anschließend für ein konkretes Wort eine TM aus durch Modifikation der Definition von per Hand. Wenn auf dem (anfangs) leeren Band gestartet wird, soll als erstes auf das Band schreiben und sich anschließend verhalten, wie , sodass .

Machen Sie sich klar, dass auf diese Weise jedem Wort je eine spezielle TM zugeordnet werden kann.

Lösung

Die erste TM berechent die Formel , 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 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 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 die Ausgabe berechnet. Zusammen ergeben diese beiden TM eine TM, die das Halteproblem berechnet ().

• 1, wenn stoppt, gdw. stoppt und stoppt.
• 0, wenn nicht stoppt, gdw. stoppt und stoppt.

Damit ist ein Widerspruch erzeugt.