Turingmaschinen

Question

Hallo,

leider fehlt mir der Ansatz wie man Turingmaschinen angeben kann.
Die Aufgabe 5, Übungsblatt 3, kann ich beispielsweise nicht nachvollziehen. Die Übergänge sind mir nicht klar.

Haben Sie einen Tipp, wie man allgemein bei solchen Aufgaben vorgeht?

Vielen Dank!

Answer 1

Also vorneweg, die Aufgabe HU-3-2 (das ist Aufgabe 5 vom 3. Übungsblatt - Sie sollten möglichst im Forum immer die ID benutzen) gehört zu den allerschwersten Aufgaben, die wir überhaupt in den Übungen stellen. Vor allem vom Umfang her geht das auch weit über das hinaus, was wir in einer Klausur fragen würden! (Sowohl der a)-Teil als auch noch mehr der b)-Teil.) Die Konzepte, die dort verwendet werden, etwa der Binärzähler, sollten Sie aber von der Idee her schon verstanden haben. (Wobei auch der b)-Teil etwas einfacher ohne Binärzähler implementiert werden könnte.)

Ein Tipp bei Aufgaben, wo die Lösung bekannt ist und Sie sie nicht verstehen, ist natürlich, die Übergänge im XWIzard nachzuvollziehen. In diesem Fall wäre das für den b)-Teil dieser Link. Das sieht zunächst etwas unübersichtlich aus, aber beim zweiten Hinsehen erkennt man schnell die unterschiedlichen Programmbereiche, wie sie auch weiter unten in der Lösung erklärt und auch graphisch dargestellt sind. Auf diese Weise versteht man - mit etwas Anstrengung - sehr gut, wie die einzelnen Zustandsübergänge wirken und zu den gewünschten Abläufen entlang dieser Programmbereiche führen. (Am besten laden Sie die PDF herunter, dann können Sie leichter hineinzoomen.)

In diese Richtung geht auch mein zweiter Tipp: Sie sollten sich die Übergangstabelle einer Turingmaschine immer als ein Programm vorstellen. (Im Lehrbuch sprechen wir auch vom "Turingmaschinenprogramm".) Wenn man etwas Übung hat, unterscheidet sich das Programmieren einer Turingmaschine nicht so sehr vom Schreiben eines Java-Programms (oder eines Programms in einer anderen gängigen Programmiersprache). Sie sollten sich zunächst überlegen, welche unterschiedlichen Teilaufgaben das Programm lösen soll und diese dann nacheinander in Zustandsübergänge umsetzen. Wenn wir den einfacheren a)-Teil der von Ihnen angesprochenen Aufgabe betrachten, kann man sagen, dass es drei relativ abgetrennte Bereiche gibt:

1. Prüfen, ob "das aktuelle" Zeichen in der vorderen Hälfte dasselbe ist wie das entsprechende Zeichen in der hinteren Hälfte.
2. Das "aktuelle" Zeichen wird dabei durch die Position des rechtesten bisher geschriebenen $K$ bezeichnet. Daher muss während des Prüfens jeweis das abgearbeitete Zeichen vorne und hinten durch $K$ überschrieben werden.
3. Falls die vordere Hälfte abegearbeitet ist, also keine Nicht-$K$-Zeichen mehr enthält, prüfen, ob auch die hintere Hälfte keine weiteren Zeichen enthält (also wirklich eine "Hälfte" ist und nicht länger).

Diese drei Bereiche müssen durch Turingmaschinenübergänge umgesetzt werden, was aber relativ einfach möglich ist. Einen guten Blick zu entwickeln, welche Aktionen eine Turingmaschine leicht ausführen kann und wie diese Aktionen zu einem bestimmten Zweck eingesetzt werden können, ist der Knackpunkt, und das geht letztendlich nur mit Übung. Die drei gerade beschriebenen Bereiche sind aber ganz typisch und werden in der einen oder anderen Form in vielen unserer Aufgaben verwendet.

Ich würde vorschlagen, Sie versuchen, mit meiner Erklärung das Programm etwas besser zu durchschauen und melden sich nochmal, wenn Sie weiterhin Probleme haben.

Comments

Vielen Dank!
Ist es ausreichend die Zustandsänderungen, wie beim XWizard, hinzuschreiben oder wird die Tabelle auf dem Lösungsblatt verlangt?

---

Das können Sie machen, wie Sie wollen, beides geht und beides werten wir gleich. Manchmal geben wir in der Klausur allerdings eine Turingtafel vor, und dann bietet es sich natürlich an, diese zu nutzen.