Turingmaschine

[ProjectLg]

Hallo,

ich bereite mich gerade auf eine Klausur in der nächsten Woche vor. Leider komme ich bei einer Übungsaufgabe nicht weiter. Die Turingmaschine zur unären Addition habe ich noch hinbekommen, allerdings hänge ich nun bei der Turingmaschine, die unäre Zahlen aufsteigend sortiert. (Trennung der Zahlen z.B. durch Bindestrich oder Komma) Es müssen auch nur 2 Zahlen sortiert werden.

Beispiel:

11-1 --> 1-11

Bitte um Hilfe, da ich keine Lösung finde.

Danke

[flashpixx]

Was hast Du denn bisher zur Lösung unternommen? Im Moment klingt das sehr nach einer Hausaufgabe. Zeige hier bitte Deine Lösungsansätze.

Als Hinweis, man kann sich hier eine Subtraktion zu nutze machen

[oxygen]

Wenns erweiterbar auf mehrere Zahlen sein soll, würde ich auch einen Bubblesort zum beispiel in betracht ziehen.

[ProjectLg]

Danke für den Hinweis. Habe nun die Subtraktion versucht(war auch eine Übungsaufgabe). Wie komme ich allerdings nun zu meiner Aufgabe?

Subtraktion:

(Aktueller Zustand; gelesenes Zeichen, geschriebenes Zeichen, Richtung, neuer Zustand)

(z0,1,1,R,z0)

(z0,-,-,R,z1)

(z1,1,1,R,z2)

(z2,#,#,L,z3)

(z2,1,1,R,z7)

(z3,1,#,L,z4)

(z4,#,#,L,z4)

(z4,1,#,L,z5)

(z5,1,1,L,z5)

(z5,#,#,R,z6) z6=Endzustand

(z7,1,1,R,z7)

(z7,#,#,L,z8)

(z8,1,#,L,z9)

(z9,1,1,L,z9)

(z9,-,#,L,z10)

(z10,#,#,L,z10)

(z10,1,#,R,z1)

[flashpixx]

@oxygen: Das geht nicht so, denn Du hast die Zahlen unär codiert und kannst nicht vergleichen nach < bzw >.

@ProjectLg: Schaue ich mir an, muss ich aber selbst per Hand durch gehen und das dauert ein wenig. Idee ist eben, dass Du von der ersten Zahl unär die zweite abziehst, d.h. entfernst, wenn das geht ist damit die erste Zahl größer als die zweite. Wenn nicht, dann stehen die Zahlen schon in der korrekten Reihenfolge. ich würde es so machen: 11 unär) | (Trenner) 1 => 10 | 1 | 1 => 9 | 1 | 2 .... => 2 | 1 | 9 => 1 | 1 | 10 => 1 | | 11 => 1 | 11

Das ganze wird relativ aufwendig. Für mehrere Zahlen würde ich das ganze dann rekursiv machen (Formaler Beweis über mü-Rekursion)

[oxygen]

ok, mit unär hab ich noch nicht gearbeitet. Dann ist wohl die Subtraktion die beste Lösung. Hab jetzt einfach mal aus den Problemen, mit denen ich in der Richtung schon gearbeitet habe drauf geschlossen, dass ein Bubblesort eine gute Lösung wäre.

[ProjectLg]

@ flashpixx: ich verstehe zwar wie deine Vorgehensweise sein soll, bekomme das Prinzip allerdings nicht in Form einer Turingmaschine dargestellt. Kannst du mir vielleicht sagen, an welcher Stelle ich meine Subtraktion ändern müsste?

[flashpixx]

Sorry, ich bin noch nicht dazu gekommen und habe die Woche viel um die Ohren, deswegen kann ich Dein Bsp nicht per Hand durchgehen.

Meine Idee war folgende, da bei der TM der Bandanfang fix ist, habe ich folgende zwei Fälle:

a) Zahl 1 ist kleiner Zahl 2 => führt direkt zum Abbruch, denn wenn ich nun unär die Zweite Zahl "strichweise" von der ersten abziehe (d.h. ich lösche einfach so lange einen Strich der ersten Zahl, bis mein erstes Zeichen das Trennerzeichen ist), dann habe ich als erstes Zeichen auf dem Band ein Trennerzeichen und es gibt noch Striche nach dem Trennerzeichen, d.h. ich muss dann eben alle Operationen wieder rückgängig machen und kann das Problem entscheiden => Zahlen sind sortiert, da ich auch zeigen kann, dass die TM nach endl vielen Schritten hält

Zahl 2 kleiner Zahl 1 => ich beginne analog und irgendwann habe ich die Zahl 1 - Zahl 2 (unär), dann Trennerzeichen und noch ein Trennerzeichen, danach dann die Zahl 2. D.h. ich nehme von Zahl 2 einen Strich weg, schaue ob ich noch einen Strich von Zahl 1 habe und schreibe diesen hinten an meine Operationen. Damit habe ich, wenn die Zahl 2 "0" ist, vor dem ersten Trennerzeichen genau "Zahl 1 - Zahl 2 || Zahl 2" stehen. Nun dupliziere ich die Zahl 2 noch einmal "Zahl 1 - Zahl 2 || Zahl 2 | Zahl 2" und nun schreibe ich den ersten Block einfach nach hinten "|| Zahl 2 | Zahl 2 + Zahl 1 - Zahl 2", zu Beginn noch die beiden Trenner entfernen und Du hast die Zahlen sortiert. Halteproblem und Entscheidbarkeit kann man analog zeigen.

Zum Aufschreiben: "Zerlege" einfach diese TM. D.h. Du baust eine TM, die einfach nur Striche kopiert, eine, die die Subtraktion berechnet usw. Dann kannst Du einfach Deine komplette TM aus kleinen Teil-TMs zusammen bauen. Wenn Du das wieder formal so machst, dass Du für jede TM zeigst, dass sie hält / entscheidet, dann kommst Du auf die Idee der mü-Rekursionen und hast somit auch gezeigt, dass Deine ganze TM funktioniert.

Ist vielleicht, wenn Du es wirklich als Zustandsdiagramm machst, eine Menge Schreibarbeit, aber es müsste so funktionieren