Turingmaschine, IT-Handbuch Kersken

[FrankSchl]

Vermutlich ganz einfach, aber....

Moin,

ich lese gerade aus Spaß an der Freud (als Amateur sozusagen) das „Handbuch für Fachinformatiker“ - laut meinen Quellen DAS Standardwerk für Fachinformatiker - und stehe bei Seite 100, Skript Turing-Maschine auf dem Schlauch.

M.E läuft der Mechanismus so ab: Der Zeige wandert so lange nach rechts, bis er auf eine Leerstelle trifft, in die er ein Y schreibt. Dann wandert er so lange nach links bis er eine 0 oder 1 findet. Nachdem er den Wert mit einem X überschrieben hat, beginnt wieder die Wanderung nach rechts. Via der Verzweigung (Zustand 5: 0, Zustand 6:1) wird das Y mit dem gefundenen Wert überschrieben. Dann wird ein neues Y gesetzt etc. Am Ende sind alle ursprünglichen Werte ge-„X“-t und stehen auf der rechten Seite in umgekehrter Reihenfolge.

Ich verstehe aber nicht, wie der Prozess sauber abgebunden wird. Ist der letzte Wert gefunden müsste, er doch eigentlich in Zustand 4 irgendwie an das Ende springen. Macht er aber in Zustand 3 . Müsste die Zeile .,7,- nicht in Zustand 4 stehen? Stehe ich da auf der Leitung?

Gibt’s da einen Experten der das erklären kann? Denn die darauf folgende Programmieraufgabe war so simpel, dass ich glaube, ich hab nur ´n Knoten im Kopf.

[TooMuchCoffeeMan]

Puh, da muss ich ganz tief in meinem Gehirn kramen, da das Wissen aus dem zweiten Semester Informatik ist. 

Ich kenne das derzeitige FiSi Handbuch nicht, aber ich vermute mal dort ist eine deterministische Turingmaschine dargestellt. Dort gibt es normalerweise im beschreibenden Tupel ein F aus der Grundmenge, das als akzeptierter Endzustand gilt. Sobald dieser Endzustand erreicht wird, endet die Berechnung. Natürlich davon ausgehend, dass es sich um eine endliche Turingmaschine handelt.

[FrankSchl]

Puh, das ging ja schnell. - Es handelt sich um das Skript 2.19:

http://openbook.rheinwerk-verlag.de/it_handbuch/02_004.html#dodtp674d2a9d-7563-4a6e-b51b-0d36407663d5

Komme bei aller Mühe nie in Zustand 7.

Ist vielleicht wirklich etwas viel verlangt. Danke jedenfalls für die Antwort.

[tkreutz2]

Vielleicht hilft ja ein Simulator das Verständnisproblem zu lösen. Es gibt doch zahlreiche Online Apps hierzu z.B.

https://turingmachinesimulator.com

http://ais.informatik.uni-freiburg.de/tursi/

[Rienne]

vor 6 Stunden schrieb FrankSchl:

Ich verstehe aber nicht, wie der Prozess sauber abgebunden wird. Ist der letzte Wert gefunden müsste, er doch eigentlich in Zustand 4 irgendwie an das Ende springen. Macht er aber in Zustand 3 . Müsste die Zeile .,7,- nicht in Zustand 4 stehen?

Ja!

vor 6 Stunden schrieb FrankSchl:

Stehe ich da auf der Leitung?

Nein!

Es scheint sich tatsächlich um einen Druckfehler zu handeln. Zumindest komme ich beim Durchgehen auf das selbe Ergebnis.

[lessbess]

Ich denke du hast Recht. Scheint ein Fehler in dem Dokument zu sein.

[FrankSchl]

Wow. Ich glaube, hier bleibe ich...

Danke an Rienne und an lessbess, die ins Buch geschaut und nachgeprüft haben.

Bin geplättet, dass es tatsächlich ein Fehler im Buch ist.

Gefällt mir aber dennoch, was der Herr Kersken da so schreibt - und lese weiter. Ciao.