TuringMaschine Dualzahlen addieren |
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
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
Phoney hat dieses Bild (verkleinerte Version) angehängt:
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Phoney: 13.12.2006 20:08.
|
|
13.12.2006 20:07 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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
|
|
14.12.2006 08:09 |
|
|
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
|
|
Hallo.
Zitat: |
Aber ich denke da ist ein Druckfehler bei dem Übergang von Zustand 6 zu Zustand 7 |
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
|
|
15.12.2006 13:21 |
|
|
|