Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Question

Hier finden Sie eine Auflistung von alternativen Lösungsvorschlägen inkl. Beurteilung aus dem alten ILIAS-Forum (vor WS1415).

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

 

Answer 1

Wäre diese Lösungsversuch der einen Zustand weniger benötigt auch korrekt?

Comments

Ja, ich würde sagen deine TM funktioniert.

Sven (Tutor)

Answer 2

Sprich irgendetwas gegen diese deutlich kürzere Variante?

(s0, 1)  (s1, E, R)
(s0, 0)  (s2, N,R)

(s1, 1)  (s1,1,R)
(s1, 0)  (s1,0,R)
(s1,*)  (s3,0,L)

(s2,1)  (s2,1,R)
(s2,0)  (s2,0,R)
(s2,*)  (s4,1,L)

(s3,0)  (s3, 0,L)
(s3,1)  (s3,1,L)
(s3,E)  (s0,1,R)

(s4,0)  (s4,0,L)
(s4,1) (s4,1,L)
(s4,N) (s0,0,R)

S0 = Nächstes Element markieren durch E oder N
S1 = Durchwandern bis zum Schluss und Komplement schreiben
S2 = Durchwandern bis zum Schluss und Komplement schreiben
S3= Zurück zum nächsten Zeichen der Binärzahl, Überschreiben der Markierung
S4= Zurück zum nächsten Zeichen der Binärzahl, Überschreiben der Markierung

Comments

Hallo,

das Problem mit dieser Variante ist, dass die TM nicht erkennen kann, wo die Grenze zwischen dem Teil, der ursprünglich auf dem Band stand, und dem Teil, den sie selbst geschrieben hat, ist. Deshalb läuft sie unendlich weiter.

Bspw.

0011 ==> N0111 => NN1111 => NNE1110 => NNEE1100 => NNEEE1000 => ...

Viele Grüße

Lukas König

Answer 3

Hallo,

habe eine etwas andere TM geschrieben und würde gerne wissen, ob sie stimmt.

Mein Gedanke war, anders als in der Musterlösung, nicht E und N am Ende auf einmal zu überschreiben, sondern nach dem das Komplement von E und N geschrieben wurde, wieder nach links zu laufen und dieses Zeichen direkt wieder durch eine 0 bzw. 1 zu erstezen und danach weiter zu machen.

Ich bin mir nicht ganz sicher, ob man das so machen darf, weil man dann ja die TM für eine kurzen Moment nicht weiß, was schon bearbeitet wurde und was nicht. Aber ich dachte mir, dass wenn der Zeiger danach eine Position nach rechts geht und das nächste Zeichen direkt wieder umwandelt, dürfte das doch kein Problem sein, oder?

Meine TM siehe im Anhang.

Bin mir halt etwas unsicher, weil meine TM so viel kürzer ist als in der Musterlösung.

Schonmal Danke für die Hilfe

Comments

Hallo,

soweit ich das sehe, ist das Problem bei deiner Turingmaschine, dass du direkt neben das ursprüngliche Wort das Komplement in Form von nullen und einsen schreibst. Daher kann die Turingmaschine nachher nicht mehr erkennen, wo dein ursprüngliches Wort aufhört. Das führt dazu, dass sie niemals stoppen wird. Stattdessen hängt sie immer mehr Zeichen hinten an das Wort dran.

Gruß

Lukas (Tutor)

Answer 4

Funktioniert der hier? Danke!

Comments

Für mich sieht deine TM korrekt aus.

Tobias (Tutor)