Beträgt die Anzahl der Schritte, falls x=b, nicht 2|vx|+5, statt 2|vx|+7?

Question

Hallo,

falls x=a bei der optimierten Variante der Turingmaschine gilt, läuft die Turingmaschine |vx|+3 Schritte. Bis hierhin ist mir die Lösung klar. Nun ist meine Überlegung:

Falls x=b gilt, läuft die Turingmaschine zuerst die |vx|+3 Schritte und "sieht" dann, dass der letzte Buchstabe ein b ist. Somit läuft die Turingmaschine bis ganz nach links zum ersten Stern (+(|vx|+1) Schritte), dann einen Schritt nach rechts (+1 Schritt) und überschreibt dort das falsch gesetzte a mit einem b. Somit wären das |vx|+1+1 = |vx|+2 Schritte mehr als für den Fall x=a. Also würde so für x=b die Anzahl der Schritte 2|vx|+5 betragen.

Habe ich irgendwo einen Denkfehler?

Vielen Dank im Voraus!

Liebe Grüße

Answer 1

Hallo,

du hast recht, da hat sich ein Fehler in der Musterlösung eingeschlichen. Allerdings ist die Schrittzahl dabei nicht IvxI + 5, sondern IvxI + 6.
schau dir am besten einmal die arbeitsweiese der Turingmaschine bei er Abarbeitung eines Wortes auf dem X-Wizard an (siehe Tabellen in Musterlösung). Wichtig ist dabei, dass der letzte Schritt, das Schreiben von b auch ein Arbeitsschritt der Turingmaschine ist. Ich glaube das Problem ist dabei, dass man einen Schritt hier nicht mit einer Bewegung des Schreib-/Lesekopfes verwechselt werden darf.

Liebe Grüße

Verena (Tutor)

Comments

Hallo,

die Bewegung des Kopfes + Überprüfen des Zeichens + Schreiben eines neuen Zeichens sind also insgesamt 2 Arbeitsschritte (bewegen+schreiben)?
Und ganz zu Anfang sitzt der Lesekopf schon über dem linkesten Zeichen der Bandinschrift?

Wäre auch als Alternativlösung denkbar, zuerst nach ganz rechts zu wandern, das letzte Zeichen zu überprüfen und zu Speichen (je ein Zustand für "es ist ein a" bzw "b"), und dann nach ganz links zu wandern und das entsprechende Zeichen vor die Bandinschrift zu setzen?

Vielen Dank und liebe Grüße!