Turingmaschine zwei Dualzahlen addieren

Wissenschaft Informatik
#1

Moin!

Ich versuche gerade, das Prinzip der Turingmaschine zu verstehen. Die Logik kann ich aber nicht durchschauen.

Angenommen, ich möchte mit Hilfe der Turingmaschine zwei Dualzahlen der Form 101 und 101 addieren, herauskommt dann ja sogar 1010. Das vierte Bit - die eins, da weiss ich schon einmal nicht, wie die ueberhaupt geschrieben werden sollte.

Ok, sagen wir einfach, die Bandposition ist

101 X 101 (#)#

Wobei der Zeiger auf der eingeklammerten Raute steht. Das X trennt die Zahlen.

Die Turingmaschine geht logischerweise erst einmal um einen nach links. und trifft dann auf die 1.
JEtzt muss ich ja quasi von ## 10[1] X 10(1) ##

kommen und das addieren. Das heißt, er muss bis zum X gehen, dann einen nach links und die 1 addieren. Zusaetzlich muss aber doch die zweite Zahl (die hintere) komplett ueberschrieben werden, samt X, für den Übertrag, oder nicht?

Vielleicht könnt ihr mir dazu ja ein bisschen erzählen. Vielleicht finde ich da auch etwas im Internet zu, aber ich habe nur einen Zustandsgraphen (?) gefunden, den ich aber nicht durchschaut habe.

Mit freundlichen Grüßen
McMike

#2

Angenommen, ich möchte mit Hilfe der Turingmaschine zwei
Dualzahlen der Form 101 und 101 addieren, …

Hallo McMike,

am einfachsten geht das mit einer Mehr-Spur-Turingmaschine.
Die hat mehrere Spuren übereinander und der Lesekopf kann
übereinanderliegende Zeichen aller Spuren
gleichzeitig auslesen bzw. beschreiben.

10(1)

10(1)

101(0)

Mehrere Spuren lassen sich auf eine Sour zurückführen,
indem das Band-Alphabet entsprechend angepasst wird
und jede vorkommende Zeichenkombination auf ein Zeichen
abgebildet wird. (z.B. 110 -> ‚6‘ etc.)

Für den Einstieg mit Turingmaschinen eignen sich einfachere Probleme,
wie z.B. zu erkennen, ob auf dem Band zuerst ‚0‘ gefolgt von ‚1‘ steht
und die Anzahl beider Zeichen gleich ist.

Grüße
Thorsten

#3

Hallo,

Angenommen, ich möchte mit Hilfe der Turingmaschine zwei
Dualzahlen der Form 101 und 101 addieren, herauskommt dann ja
sogar 1010.

Autsch, das wird aufwändig :wink:

Das vierte Bit - die eins, da weiss ich schon
einmal nicht, wie die ueberhaupt geschrieben werden sollte.

Ok, sagen wir einfach, die Bandposition ist

101 X 101 (#)#

Wobei der Zeiger auf der eingeklammerten Raute steht. Das X
trennt die Zahlen.

Die Turingmaschine geht logischerweise erst einmal um einen
nach links. und trifft dann auf die 1.
JEtzt muss ich ja quasi von ## 10[1] X 10(1) ##

kommen und das addieren. Das heißt, er muss bis zum X gehen,
dann einen nach links und die 1 addieren. Zusaetzlich muss
aber doch die zweite Zahl (die hintere) komplett
ueberschrieben werden, samt X, für den Übertrag, oder nicht?

Ich würde folgendermaßen vorgehen:
Du ersetzt jede verarbeitete 0 durch ein A, und jede verarbeitete 1 durch ein B.
Dann hast du sowas hier:
##101X10(B)##
Von jetzt an brauchst du drei parallele Stränge in deinem Zustandsautomaten: einen für eine gelesene 0, einen für 1 (ohne Übertrag) oder 0 mit Übertrag von vorher, und einen für 1 und 1 Übertrag.
Dann gehtst du bis zum X, und dann bis zur nächsten 0 oder 1, die du dann wieder ersetzt:
##10(B)x10B##
Ab jetzt brauchst du sogar vier parallele Stränge (0,1,10,11).
Dann läufst du weiter bis zum nächsten #, dann an allen As und Bs vorbei, und schreibst dann beim nächsten # das Ergebnis rein:
#(0)#10BX10B##
Jetzt gehst du in einem von zwei Strängen (Übertrag 0 oder 1) zurück bis hinter das X, dann bis zum ersten A oder B, und dann eins nach links.
#0#10BX1(0)B##
Das ersetzt du wieder durch ein A, und gehst in den Strang, der einer 1 (0 + Übertrag 1) entspricht:
#0#10BX1(A)B##
dann wieder bis zur Null nach rechts usw.

Viel Spass beim ausprobieren und debuggen :wink:.

Ich erinnere mich noch an eine Informatik-Hausaufgabe (Schule), bei dir wir einen Automaten schreiben sollten, der eine Bitsequenz über ein bestimmtes Zeichen kopieren sollte - das war schon spaßig :wink:

Grüße,
Moritz

#4

Moin.

Also das Prinzip ist mir ein bisschen klar geworden. Aber die Logik nicht ganz.

Ums einfach zu machen:

Ich möchte die Duazhal 0 und 1 addieren, habe dann auf dem Band

# 0 X 1 (#)

An der eingeklammerten Stelle ist mein Zeiger.

Ich gehe einen nach links

# 0 X (1) #

und schreibe nun für die 1 ein B.

# 0 X (B) #

Nun gehe ich nach links zur ersten Stelle nach dem x und schreibe ein A

# 0 (X) B #

# (A) X B #

So, und nun gehe ich zwei weiter nach links

# (#) # A X B #

und schreibe da nun eine 1 hin

# (1) # A X B #

Nun überschreibe ich den ganzen Rest

# 1 # # # (#)

Und wie ist nun gewährleistet, dass # # ->1 Zustand 1
0 für 0, links => Zustand 3.

Geht das? Kann man vom zweiten Zustand in zwei verschiedene Zustände für zwei verschiedene Situationen? Habe gerade ein Brett vor dem Kopf!

Ansonsten waren es beides sternchenwürdige Antworten. Wobei ich nach der mit dem Einband gefragt hatte. Wobei das mit dem zweiten auch ein toller Hinweis war, der mich sehr gefreut hat.

MfG
McMike

#5

Hallo,

Ich möchte die Duazhal 0 und 1 addieren, habe dann auf dem
Band

# 0 X 1 (#)

An der eingeklammerten Stelle ist mein Zeiger.

Ich gehe einen nach links

# 0 X (1) #

und schreibe nun für die 1 ein B.

# 0 X (B) #

Nun gehe ich nach links zur ersten Stelle nach dem x und
schreibe ein A

# 0 (X) B #

# (A) X B #

So, und nun gehe ich zwei weiter nach links

# (#) # A X B #

und schreibe da nun eine 1 hin

# (1) # A X B #

Nun überschreibe ich den ganzen Rest

# 1 # # # (#)

Und wie ist nun gewährleistet, dass # # ->1

1 Like
#6

Und wie die A, B und X am Ende ueberschreiben?
Guten Abend.

Ja, danke. Das hat es total getroffen.

Aber eins verstehe ich leider noch gar nicht. Nämlich, wir haben am Ende fiktiv

Zahl 3 # A B A X B B A # #

JEtzt habe ich nicht verstanden, wie das Programm terminiert bzw. wie gewährleistet ist, dass das Ergebnis (Zahl 3) nicht überschrieben wird.

Also, die Idee, die ich aus deinen Antworten interpretiert habe, war die, dass wir rechts anfangen, nehmen gleich die erste Ziffer, gehen zur ersten (hinteren) Ziffer der Zahl 2.
Lassen dann vom leeren Band ein „Platz“ und schreiben davor dann das Ergebnis

Also 1100 # Zahl2XZahl1 # # #

(Nur willkürliche Beispiele)

Aber am Ende haben wir ja noch für Zahl 2 und Zahl 1 eine Folge von A, B,… Das Programm würde nach meinem jetzigen Gedankensatz nicht beenden und dann das Ergebnis überschreiben.

Irgendwo scheine ich etwas falsch verstanden zu haben.

ODer wird das schon überschritten, sobald man nach rechts geht und die ersten Ziffern für das Ergebnis geschrieben hat?

Wäre schön, wenn man mir da noch einmal helfen kann.

Liebe Grüße
McMike

#7

Aber eins verstehe ich leider noch gar nicht. Nämlich, wir
haben am Ende fiktiv

Zahl 3 # A B A X B B A # #

JEtzt habe ich nicht verstanden, wie das Programm terminiert
bzw. wie gewährleistet ist, dass das Ergebnis (Zahl 3) nicht
überschrieben wird.

Also, die Idee, die ich aus deinen Antworten interpretiert
habe, war die, dass wir rechts anfangen, nehmen gleich die
erste Ziffer, gehen zur ersten (hinteren) Ziffer der Zahl 2.
Lassen dann vom leeren Band ein „Platz“ und schreiben davor
dann das Ergebnis

Also 1100 # Zahl2XZahl1 # # #

(Nur willkürliche Beispiele)

Aber am Ende haben wir ja noch für Zahl 2 und Zahl 1 eine
Folge von A, B,… Das Programm würde nach meinem jetzigen
Gedankensatz nicht beenden und dann das Ergebnis
überschreiben.

so wie sich das für mich darstellt, wandert der Lesekopf nach der (erfolgreichen) Addition wieder nach rechts und sucht eine neue noch nicht mit A oder B überschriebene Ziffer. Findet er sie nicht, solange er rechts vom Trennzeichen # ist, so könnte die Maschine einfach in einen neuen Zustand gehen, und wieder nach rechts wandern und alle B und A mit der ursprünglichen Belegung (1, 0) überschreiben. Wenn der Lesekopf bei # ankommt ist der Endzustand erreicht.
–> terminiert