Turing Maschine

K

Kenniej91

0
Hi, ich wusste nicht genau wohin mit dem Thema, also hier her.
Halte morgen ein Referat und wollte überprüfen ob ich alles richtig verstanden habe:
Ich wollte eine Turing Maschine entwickeln, welche 2 Zahlen addiert, wobei es immer positive ganze sind. 1 wird durch eine 10 dargestellt
2 durch 110
3 durch 1110
4 durch 11110 usw.

Es stehen dabei zwei Zahlen hintereinander und der Lese Schreibkopf ist am Anfang auf der 1 der ersten Zahl(zur Verinfachung ist diese größer gleich 1), hier also die Programm Tafel (FOrmatierung leider schlecht):

Code: 
Zustand:     Bei Eingabewert:     Schreibe Hin:      Gehe Zu Zustand:      Bewegung:
1                        -                      0                      2                         R
2                        1                      -                      2                         R
2                        0                     1                      H(Halt Zustand)  -
H                       -                      -                        -                         -
Ist das so (auch formal) richtig?
 
Bei uns sahen die Übergangfunktionen zwar anders aus, aber ich denke, das müsste formal ok sein.
Allerdings bin ich mir nicht ganz sicher, ob deine Funktion selber korrekt ist.
Begründung:

Du hast dein Band mit den zwei Zahlen, nehmen wir mal die 2 und 3. Dann sieht das so aus:

1101110

Wenn ich nun deine Funktion anwende, weiß ich schonmal nicht, wie ich deinen Zustand 1 deuten soll. Deine Eingabe ist ja nicht - sondern 1.
So, wenn du die nun addiert hast, hast du zwar die korrekte Anzahl an Einsen, da du die erste Eins an die Trennstelle zwischen den Zahlen wieder einfügst, deine Zahl hat nun aber die Form

0111110 und entspricht nicht mehr wirklich deiner Darstellungsform
 
Erstmal danke für die Antwort
Ja, also ich denke es geht auch bei diesen Modellen immer nur dadrum den Algorithmus zu beschreiben, also du hattest sicher ein anderes Modell (denke ich)
Zu dem -, dass soll heißen das dort beliebiges stehen kann, wobei ich aber auch hätte schreiben können : Zustand 1 bei Eingabe 1, Zustand bei Eingabe 2....

Zum Ergebnis, man könnte entweder sagen, dass die Zahl ja einfach nur irgendwo stehn muss, getrennt vom anderem, oder ich mache es halt so das im Zustand 1 statt ner 0 ein Leerzeichen geschrieben wird.
Sag bitte wenn du anderes denkst.
 
Also ich würde das wirklich eindeutig machen, da dein - in Zustand 1 für beliebig steht, in Zustand 2 dann für nicht schreiben.
Die Theoretiker würden zwar bestimmt noch das Ein oder Andere bemängeln (z.B. wo ist der Rest von dem 7-Tupel, das eine Turingmaschine definiert, du hast hier wirklich nur die Zustandsüberführung gezeigt), aber gerade für einen Vortrag dürfte das sonst ok sein.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben