Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

–1 Punkt
264 Aufrufe

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!

 

Gefragt 26, Nov 2014 in TUR-AF von uafjv uafjv Tutor(in) (167,990 Punkte)  

4 Antworten

0 Punkte

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

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Ja, ich würde sagen deine TM funktioniert.

Sven (Tutor)
0 Punkte
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
Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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
0 Punkte

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

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
0 Punkte

Funktioniert der hier? Danke!

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Für mich sieht deine TM korrekt aus.

Tobias (Tutor)
...