Entwickler-Ecke
Algorithmen, Optimierung und Assembler - MOD-Berechnung mit einer Turing-Maschine
ApfelSandwich - Mo 26.11.12 22:37
Titel: MOD-Berechnung mit einer Turing-Maschine
'n Abend,
vielleicht nicht zuletzt wegen dieser späten Stunde habe ich grad irgendeine Denkblockade und zweifle bereits an mir selbst.
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?
Danke für Eure Hilfe und einen schönen Abend noch
mfg ApfelSandwich
PS: Die Sektion heißt "Algorithmen", also sind auch Turingmaschinen hier am richtigen Platz, oder?
ApfelSandwich - Mo 26.11.12 23:03
Hi Mathematiker, dankeschön für Deine Antwort. Leider konnte ich in den beiden Themen keine Antworten finden. Trotzdem Danke für Deine Mühe beim Suchen.
Ich bin recht verzweifelt, was das Finden einer Lösung angeht. Sry, dass ich nicht an das Verlinken gedacht habe. Jetzt hast du es ja getan.
Einen schönen Abend noch
Mathematiker - Mo 26.11.12 23:07
Es war keine Mühe. :wink:
Aus den Regeln
| Zitat: |
3.10 Crosspostings
Stellst du die gleiche Frage auch in einem anderen Forum, dann kennzeichne deine Frage bitte entsprechend und verlinke die Topics untereinander. |
Ich habe nur das gemacht, was Du leider im Eifer des Gefechts vergessen hattest.
Beste Grüße
Mathematiker
Xion - Di 27.11.12 16:06
 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.
Fiete - Di 27.11.12 16:32
Moin ApfelSandwich,
hier ein Tip:
http://www.entwickler-ecke.de/viewtopic.php?p=510016#510016
mit dem Turingsimulator kannst Du TP's erstellen und testen.
Das m mod n TP könnte so aussehen, Alphabet aufbohren :wink: :
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| // repeat m:=m-n until m<n
// BmBnB... --> Bm1nBm1nB...
// z.B. BIIIIIIIIIIBIIIIIB... --> BIIB...
// 9 mod 4 = 1
01#B(REB)1(LIB)(DUP)(RE1)B(LIB)#02
02#B(DIF)R#03
03#BL(VZL)(RE1)BR#04
03#I(RE1)(LIB)R#06
04#IBR#04
04#B(LII)(LIB)#00
06#IBR#06
06#1B(LII)R(VZL)(LIB)#01 |
Gruß Fiete
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!