Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

0 Punkte
100 Aufrufe
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
Gefragt 5, Feb 2018 in 2017-N-03 von Anonym  

Eine Antwort

0 Punkte
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)
Beantwortet 6, Feb 2018 von updrq updrq Tutor(in) (103,620 Punkte)  
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!
...