Turingmaschine; Zahlenvergleich
-
Hey,
also erstmal falls das hier das falsche Unterforum für die Turingmaschine ist, bitte verschieben. Dachte hier könnte es am ehesten hereinpassen...
Also es geht um den Vergleich zweier unärer Zahlen.
Dabei ist das Band z.B. so belegt: 111?11111 .
Nun soll das '?' durch den passenden Vergleichsoperator '=' , '<' oder '>' ersetzt werden.Die Frage ist nun: Kann ich die Anzahl der Stellen der ersten und zweiten Zahl irgendwie zählen? Ich kann ja nicht immer in einen neuen Zustand pro weitere Stelle übergehen, da es im Prinzip unendlich viele geben kann.
Oder gibt es da einen anderen Trick?Ein Tipp wäre hilfreich!
MfG
-
Du könntest neue Symbole für eine "gezählte 1" und eine "gezählte 0" einführen. Dann ersetzt du immer abwechselnd in den beiden zahlen ungezählte symbole durch gezählte. Wenn du bei einem früher fertig bis als beim anderen, dann ist die zahl kürzer.
Wenn du dann gleiche länge rausbekommst sollte sichd er rest ja leicht machen lassen.
-
Grundidee: Fährst ganz nach rechts, löscht eine 1, fährst dann ganz nach links, löscht eine 1 und beginnst wieder von vorne.
Und dann mal überlegen, wie beendet wird. Hmm, vielleicht fährt man in eine Richtung bis auf die 0, fährt eine Stelle zurück, und schaut
-wenn man auf einer 1 gelandet ist, macht man sie weg rauscht ans andere Ende
-wenn man auf einem Vergleichsoperator gelandet ist, sollte man den Rest mit wenigen Zuständen auswerten können.
-
Danke!! Hat mir sehr geholfen, beide Beiträge