Wie schreibe ich eine Turingmaschine, die eine Zahl nach rechts verschiebt?
Hallo,
ich solle eine Turing-Maschine angeben, die eine 1 nach rechts verschiebt, wobei der Abstand zu einer weiteren 1 um eine 0 verringert wird.
Wie kann man dies angeben?
Muss ich ganz links/rechts starten?
LG
Hier noch die Aufgabe. Stimmt das oder wie gibt man die Zustände jeweils an?
Danke im Voraus
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik
Du bewegst den Kopf zum Ende des Wortes. Der Kopf steht nun hinter dem Wort.
Du führst folgendes durch:
- Steht der Kopf auf dem Zeichen hinter dem Wort, lasse das Zeichen unverändert stehen und bewege den Kopf um eins nach links.
- Steht der Kopf auf einer 0, lasse diese stehen und bewege den Kopf um eins nach links.
- Steht der Kopf auf einer eins, bewege den Kopf um eins nach rechts. Dann:
- Steht dort eine 0, so ersetze diese durch eine 1 und bewege den Kopf zurück nach links. Dann ersetze die 1 dort durch ein Sonderzeichen und bewege den Kopf um eins nach links.
- Steht dort eine 1 lasse diese stehen und bewegen den Kopf um eins nach links. Lasse die 1 dort stehen und bewege den Kopf erneut um eins nach links. (Keine Lücke zwischen den einsern, also kannst du nicht verschieben.)
- Bist du am Anfang des Wortes angelangt, so durchläufst du das Wort erneut und füllst die entstandenen Lücken auf, indem du Zeichen jeweils solange nach links verschiebst bis die Lücke gefüllt ist.
Wie mit einer 1 am Ende des Wortes verfahren werden soll geht aus der Aufgabenstellung nicht hervor.
Destranix
11.01.2024, 11:13
@maria1811
Z2 ersetzt alle 1en durch Sternchen. Das stimmt so nicht.
Auch sonst ist die Auflistung unvollständig.Ob das Beispiel unten stimmt kann ich nicht sagen, da ich die Aufgabenstellung nicht kenne.
Danke für die Antwort! Meine Frage habe ich mittlerweile ergänzt. Wie verhält sich das mit den Zuständen, habe ich das im Beispiel richtig aufgeschrieben?