TuringMaschine Dualzahlen addieren |
| 13.12.2006, 20:07 | Auf diesen Beitrag antworten » | ||
| Phoney | TuringMaschine Dualzahlen addieren Hallo. Ich möchte gerne folgendes Beispiel der Dualzahlenaddition verstehen (aus dem PDF http://www.bw.fh-deggendorf.de/kurse/wi_...ten/skript1.pdf Seite 13) (Oder siehe Anhang) Was genau passiert vom Zustand 6 in den Zustand 7? Das verstehe ich nicht ganz. Also vorher ist es ja so: Wir haben das Band . . 101 . 0 0 1 . . unser Lesekopf befindet sich auf dem Punkt, der die Zahlen trennt . . 1 0 1 (.) 0 0 1 . . So, nun gehen wir so lange nach rechts, bis wir die 1 finden . . 1 0 1 . 0 0 (1) . . Die ersetzen wir durch eine Null und gehen so weit nach links, bis wir nach dem . angekommen sind, der die Zahlen trennt. . . 1 0 (1) . 0 0 0 . . So, und nun sind wir schon in Zustand 6. Er schreibt für die 1 eine Null (klar, wegen dem Übertrag) und geht um einen nach links 1 (0) 1 . 0 0 0 Und jetzt steht da ja, bei 6. Schreibe so lange für eine Eins eine Null und gehe nach links , bis du bei 1,0 ankommst und gehst nach Rechts? Lese ich das falsch? Heisst das vom Zustand 6 nach Zustand 7: Für eine 1, schreibe eine 0 und gehe nach rechts. Das stimmt doch?! Und dann steht da ja .,1,R Auch noch durch den Übertrag bedingt. Aber was ist, wenn dort eine Null steht? Ist diese Turing Maschine überhaupt auf mein Beispiel des Bands . . 101 . 0 0 1 . . übertragbar? Viele Grüße Phoney |
||
|
|
|||
| 14.12.2006, 08:09 | Auf diesen Beitrag antworten » | ||
| ed209 | Die Turingmaschine subtrahiert regelmässig eins bei der rechten zahl (Zustände ,4,5) und addiert dann eins auf die linke Zahl (Zustände 6,7). Aber ich denke da ist ein Druckfehler bei dem Übergang von Zustand 6 zu Zustand 7, denn die beschreibung aus dem Bild ist die einer nicht-deterministischen Turingmaschine: Zustand 6 beschreibt zwei verschiedene Verhaltensweisen wenn eine eins auf dem Band gefunden wird (1,0,R) und (1,0,L). Ändert man aber ersteren in (0,1,R) dann arbeiten die Zustände 6 und 7 wirklich so daß zu einer Zahl 1 addiert wird. Es werden von rechs solange alle einsen auf null gesetzt bis eine 0 oder ein Blank kommt die dann auf 1 gesetzt wird. Gruß, ED209 |
||
| 15.12.2006, 13:21 | Auf diesen Beitrag antworten » | ||
| Phoney | Hallo.
Ah, das dachte ich auch bzw. ich habe den Sinn da nicht verstanden. Danke dir für deine ausführliche Erkärung! Grüße Phoney |
||
|
|
