Entwerfen Sie eine Turingmaschine

Question

Frage:

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? (Hab die selbe Frage aus Versehen im Matheforum gestellt) 

Answer 1

Hm

ich hab sowas wie eine Turing maschine in geogebra gebaut. nach

https://turingmachinesimulator.com/

modulo 5, (muß ja nicht wirklich was gerechnet werden)

suche letzte ziffer

letzte ziffer 0 : fertig rest 0

letzte ziffer 5 : fertig rest 0

letzte ziffer 1,2,3,4 : fertig rest 1,2,3,4

letzte ziffer 6,7,8,9 : fertig rest 1,2,3,4

Comments

Dankeschön! Hast Du ne Ahnung, wie man bei b) vorgeht?

---

zu dem beispiel

Mir hat es enorm geholfen das Touring-Konzept zu verstehen mit action den nächsten schritt einsehen zu können...

Allgemeine Version:

da würd ich mal googeln ob ein (smarter) code dazu zu finden ist.

Naiv gedacht eine Division mit Rest zu bauen oder so lange den Divisor abziehen bis der Rest erreicht ist?

In dem Link oben gibt es ein Turing Code für Dez-Bin - die Division mit Rest nachbauen?