ApfelSandwich hat folgendes geschrieben : |
Ich wollte einfach eine mod-Funktion mit unären Zahlen umsetzen. Ich wollte einfach dividieren (zyklisch abziehen), bis es nicht mehr geht und dann gucken, was übrig ist. Ich habe meinen Entwurf leider auf dem Papier gemacht, hoffe ihr versteht, was ich meine.
Wie würdet ihr so ein Turingmaschinenprogramm bauen? |
So, wie du es beschrieben hast. Die einzige Schwierigkeit ist wohl, beim abziehen vorsichtig zu sein (weil du ja erst merkst, dass es nichtmehr geht, wenn du bei 0 angekommen bist). Mit einer 2-Band-Turingmaschine sollte das aber kein Problem sein.
a mod b
=>
a auf Band 1
b auf Band 2
=>
a und b gleichzeitig nach vorne laufen lassen (=1 abziehen)
b am Ende => du hast einmal b von a abgezogen => Kopf von Band 2 wieder nach vorne holen
a am Ende => diesesmal ist a 0 geworden. Die Kopfposition von Band 2 gibt dir an, wieviel du gelöscht hast, das addierst du also am Ende wieder auf Band 1. => Fertig
Es geht (natürlich) auch mit einem Band mit dem gleichen Prinzip, nur musst du dann die Bänder simulieren (ein Trennzeichen auf dem Band setzen). Ist nur etwas mehr schreib-/rechenaufwand.