Wie entwerfe ich eine Turingmaschine, die den Divisionsrest berechnet?

Question

Aufgabe:

Entwerfen Sie eine Maschine die den Divisionsrest modulo 3 berechnet. Die Maschine soll beispielsweise die Eingabe . . . * * ||||||||||| * *. . . in die Endkonfiguration . . . * * || * * . . . überführen.

Der Lese-/Schreibkopf steht
zu Beginn jeweils auf dem ersten (linken) Buchstaben des Eingabeworts.

Problem/Ansatz:

Ich hab keine Idee wie ich das entwerfen soll. Eine Maschine die zählt wie oft ganzzahlig geteilt wird habe ich hinbekommen. DIe Maschine streicht wiederholt 3 Striche, geht ans Ende und notiert wenn dies einmal geschehen ist. Wenn weniger als drei Striche übrig bleiben stoppt die Maschine. Das Problem ist, dass diese den Rest der übrig bleibt wegstreicht um in den Endzustand zu kommen. Gibt es einen Ansatz wie es möglich ist den Rest stehen zu lassen und diesen zu berechnen? Und das nicht gezählt wird wie oft die Zahl ganzzahlig hineinpasst?

Answer 1

Entwerfe einen deterministischen endlichen Automaten, der den Divisionsrest berechnet.

Ergänze den Automaten zu einer Turingmaschine.

Comments

verstehe ich nicht

---

Zustände sind \(q_0\), \(q_1\) und \(q_2\).

Anfangszustand ist \(q_0\).

Transitionen sind \(q_0\stackrel{|}{\to}q_1\), \(q_1\stackrel{|}{\to}q_2\) und \(q_2\stackrel{|}{\to}q_0\).

Wenn dieser Automat das Wort gelesen hat, dann kennt er den Divisionsrest.

Ergänzung zu einer Turingmaschine: In den Transitionen wird zusätzlich das aktuelle Zeichen gelöscht und der Lese-/Schreibkopf nach rechts bewegt. Jetzt müssen nur noch dem Zustand entsprechend viele | aufs Band geschrieben werden, falls ein * gelesen wird.