Turingmaschine Algorithmus bestimmen

[Krümelchen]

Hallo,
nachdem ich jetzt schon den ganzen Nachmittag und den Abend bei diesen Aufgaben verbringe wollte ich hier mal nachfragen.

Gibt es irgendwelche "Tricks" (außer viele zu entwickeln) um für Turingmaschinen Programme zu erstellen?
Wenn ich mir zB auf Wikipedia den Algorithmus zur verdopplung der Einsen oder hier den zum erkennen von Wörtern ansehe dann hab ich ziemliche Probleme damit zu eruieren wie man auf diesen Weg gekommen ist. Es ist doch alles etwas abstrakt. Vor allem wenn man nichtmal schöne Sprungadressen oder Zähler hat.
Und sollte man die Übergngsfunktionen großzügig gestalten oder eher weniger nehmen?

Unter anderem habe ich hier zB diesen bei dem man die Länge von zwei Wörtern bestimmen muss. Aber irgendwie weiß ich nicht ob er so passt.
Bsp: XabcdXasdfgX wird zu X111111111X

Mein Algorithmus:

Angefangen wird bei dem rechtesten X
Zustand | gelesen | schreib | neuer Zustand/Richtung
1            |   X          |             |  2,L
1             |   1         |              |  2,L
2             |a-z         |   1       |  1
2             |  X         |                |   2,L

So weit funktioniert dieser auch, ich habe aber das Problem, dass wenn jettz das mittlere X gelesen wird lässt er es weiterhin stehen und geht bis nach links zum Nächsten X.
Optimal wäre aber wenn das mittlere X gelöscht wird und wenn er ganz links oder wieder rechts ankommt, dass er hält.
Ich könnte zwar das mittlere X löschen und dann weitergehen aber was passiert dann ganz links? Dann wird er dass doch auch löschen.
Wo kann ich bei sowas ansetzen? Ich hab zwar auch probiert, dass er nach dem mittleren X nach rechts geht und dann wieder nach links in einen anderen Zustand aber dann stehe ich wieder bei dem linkesten X.

Wäre super wenn mir da jemand ein paar Tipps geben kann.

 

[kisser]

Es ist leider (oder gottseidank) schon lange her, dass ich mich mit Turing-Maschinen beschäftigen musste, so dass ich wohl hier kein große Hilfe leisten kann.

Aber bist du sicher, dass dein Endzustand so richtig ist?
Die Länge eines Wortes ist für mich die Anzahl seiner Buchstaben, so dass ich als Endzustand X4X5X annehmen würde.

Die Übergangsfunktion kann ruhig großzügig sein, da gibt es keine Beschränkung in ihrer Größe, sie muss nur eindeutig sein für deterministische Turing-Maschinen.

 

[Rabrogo]

Überprüfe ob er am Ende ist indem er noch eine Stelle weiter geht, und dabei das X stehen lässt, wenn nichts da steht, bleibt er stehen, wenn nicht geht er zurück und löscht es oder du lässt es stehen und er geht einfach weiter (deine Entscheidung, stimme Kisser im Bezug auf den Endzustand zu).

Ergänzung (2. November 2014)

was schwierig wird ist wenn du Wörter mit mehr aus 10 Zeichen hast, aber das kannst du späterlösen, wenn du das Grundgerüst hast

Ergänzung (2. November 2014)

Ein einfacherer Weg eine Übergangsfunktion zu entwickeln war für mich zuerst ein Transitionsdiagramm zuerstellen, dafür gibts auch Programme die du dafür verwenden kannst (besser zu editieren, also Zustände zu löschen, bzw. zwischen 2 Zuständen einen neuen einbinden).

 

[Ochse]

Du willst also du Summe der Längen der beiden Wörter im Unärsystem bestimmen, korrekt?
Daher ist die Formel für die Länge gleich Anzahl der Zeichen (inkl. X) minus 3 (wegen der 3 X), oder?

Ich weiß nicht ob es einen Trick gibt, aufjeden Fall ist es aber hilfreich eine möglichst einfache Grundidee zu haben und zunächst nicht mit neuen Zuständen zu geizen.

Keine Ahnung ob ich dich richtig verstanden haben aber würde folgendes tun.
1. Erstmal alles plattmachen d.h. mit '1' überschreiben und dabei solange nach links gehen bis zu einem Leerzeichen
2. Das erste X ganz links löschen und so die ganze Zeichenkette um eins verkürzen
3. Außen die Einsen durch ein X ersetzen

Also ungefähr so:


Habe angenommen, dass es zwei Wörter gibt die mindestens die Länge 1 haben und dass das rechte Ende durch ein '$' markiert ist (so wie das in deinem Link steht).
Meine Erfahrungen damit sind gefüllt Jahrzehnte her. Es könnte also kompletter Unsinn sein^^.

Edit:
Falls bei dir X und Leerzeichen das Gleiche sein sollte, müsstest du das Ganze geringfügig modifizieren. Vielleicht dann so in der Art:

 

[Krümelchen]

Jup genau, es geht um den Betrag der Wörter im unären.
@Ochse
Ahh der Ansatz ist ja ziemlich interessant.
Die Idee einfach die äußersten zu überschreiben gefällt mir.

Das Problem ist nur, dass wir es so definiert haben, dass links und rechts immer ein X stehen soll.
Ich hab mir das jetzt mal durchgedacht so wie du es meinst aber irgendwie will ich einfach nicht so Turingmäßig "denken" :/

Wobei ich sagen muss, dass wenn man es sich als Automaten darstellt gar nichtmal so schlecht ist.

@Kisser
Oh Gott,
wenn ich jettz noch etwas damit addieren müsste um es im Dezimalsystem darzustellen würde ich ja ganz verzweifeln.

 

[Ochse]

Mhh so ganz verstehe ich dich immer noch nicht^^.

Die X ganz links und rechts sind also 'schreibgeschützt' oder müssen sie nur zum Schluss wieder da stehen?
Eure Definition ist eigenartig .

Es wäre wesentlich einfacher wenn ich über alle Spielregeln aufgeklärt wäre.
Naja wie auch immer ich muss zurück in den Stall .

Edit:
Wenn ich es recht bedenke, war der Ansatz doch ziemlich umständlicher Mist.
Besser ist es einfach von rechts nach links zu gehen und jedesmal eine andere Umgangsfunktion/Zustand zu einzuführen sobald ein X gelesen oder ein X-Feld verlassen wird. Dabei können die X auch unangetastet bleiben (außer das mittlere):




Um so richtig 'Turingmäßig' zu denken, bleibt dir wahrscheinlich doch nichts anderes übrig als dir viele Turing-Maschinen anzuschauen .