Aufgabe:
a) Entwerfen Sie eine Turingmaschine, die den Divisionsrest modulo 5 berechnet. Die Maschine soll
beispielsweise die Eingabe . . .⋆⋆||||||||||| ⋆⋆ . . . in die Endkonfiguration . . .⋆⋆|⋆⋆ . . . überführen.
Beschreiben Sie dafür zunächst die Idee hinter der Maschine.
b) Angenommen, Sie wollen analog dazu eine Turingmaschine konstruieren, die den Divisionsrest modulo m für eine gegebene natürliche Zahl m bestimmt. Wie viele Zustände wird diese Maschine haben (in Abhängigkeit von m, ohne Fehlerzustände)?
Problem: Ich vermute, dass ich zunächst Zustände benötige, aber wie entwerfe ich diese Maschine?
