0 Daumen
133 Aufrufe

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?

Avatar von

Hat denn niemand eine Idee oder einen Ansatz? :p

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community