Hauptklausur 2018 Aufgabe 4 Turingmaschine

Question

Hallo, 

wie schon bei einem anderen Foreneintrag festgestellt, handelt es sich bei dieser Turingmaschine um eine Turingmaschine mit Ausgabe. Ist es richtig, dass diese keinen festen Endzustand besitzt und nur dann endet, wenn kein Zustandsübergang für das gerade gelesene Zeichen und den Zustand vorhanden ist? 

Bei der Aufgabe muss die Konfigurationsfolge angegeben werden. Meine Frage zur Lösung: Fehlt nicht der letzte Schritt in der Konfigurationsfolge? Müsste da nicht noch stehen: |--- (a, s3, cd) (und erst dann gibt es keinen neuen Zustandsübergang?!) Vielen Dank für eure Hilfe!

LG

Answer 1

Hallo uvfaj,

Sowohl bei der Turingmaschine mit als auch ohne Ausgabe ist es so, dass die TM hält, wenn der Zustandsübergang nicht mehr definiert ist, wie du es sagst. Im Tutorium hatten wir meistens Aufgaben, in denen festgelegt war, so unsere TM stoppen soll, also mit einer neutralen Endposition. Sonst könnte es sein, dass sie in eine Endlosschleife gerät, falls wir falsch modellieren. Hier ist die TM aber so definiert, dass sie automatisch richtig hält, wenn für die aktuelle Eingabe und das aktuelle Zeichen kein Übergang definiert ist.

Nein, das stimmt so wie es in der Lösung ist. In der Konfiguration steht immer als erstes das, was links vom Schreib- Lesekopf steht, in der Mitte dein aktueller Zustand und rechts, das, worauf der SL-Kopf steht sowie alles rechts davon. Wenn du es mit der Zeile drüber vergleichst, siehst du ja links nur leere Felder und ab dem SL-Kopf ein Sternchen sowie abc. Im letzten Zustand ist links nichts, und unter dem SL-Kopf steht bereits dein a. Das muss also in die aktuelle Konfiguration mit rein.

Ich hoffe, ich konnte deine Frage beantworten, sonst melde dich nochmal.

Viele Grüße

Hannah (Tutorin)