Umwandlung binär in unär?
Wie ist es möglich, eine Binärzahl (z.B. 110 = 6) in eine Unärzahl (|||||| = 6) mit einer Markov-Tafel umzutauschen?
Also dass man prinzipiell nur von links nach rechts bestimmte Zeichen mit anderen Zeichen austauschen darf mit dem letzendlichen Ergebnis von Zahl_binär --> Zahl_unär.
Ich überlege die ganze Zeit schon, wie man das realisieren könnte, da eine 1 ja z.B. immer einen unterschiedlichen Wert hat, je nachdem an welcher Stelle sie steht.
3 Antworten
Ich hätte eine Idee:
Angenommen du hast eine Binärzahl der Form b_0, b_2, ... , b_n mit b_i € {0,1}
Dann machst du folgendes: Du gehst zunächst jede Zahl b_0 bis b_n der Reihe nach durch und suchst erst nach den 1en, wenn du ein b_i findest mit b_i = 1, dann machst du folgendes: du fügst 2^(n-i) viele einsen hinzu.
Im nächsten Schritt schaust du dir an, welche b_i = 0 sind. Wenn b_i = 0, dann entfernst du 2^(n-i) viele Einsen
Dafür muss aber b_0 = 1 immer gelten
Schreibe die unäre Zahl vor die Binärzahl, z.B. ||101 (aus ursprünglich 10101). Ersetze die nächste Ziffer durch keinen oder einen neuen Strich, aber alle bisherigen Striche müssen verdoppelt werden. Dazu setzt Du eine Marke (-) hinter die noch zu verdoppelnden Striche und lässt sie nach links wandern.
Also im Wesentlichen "1 => -|", "0 => -", "|- => -||".
Beispiel:
- ||0... => ||- ... => |-|| ... => -|||| ... -> |||| ...
- ||1... => ||-|... => |-|||... => -|||||... -> |||||...
Die richtige Reihenfolge der Regeln findest Du selbst heraus.
Regel 5. scheint mir nicht zu terminieren. Soll das so?(Oder ist der Punkt dahinter Teil der Regel? Dann dürften nach Anwendung von 5. aber Punkte stehen bleiben, die mit keiner anderer regel wieder entfernt werden können.)
Ein Punkt bedeutet, dass der Algorithmus terminiert.
Verstehe. Dnan dient die Regel lediglich dazu, automatisch zu terminieren, sobald Regel 5 erreicht wird.
Genau! In einer Markov-Tafel kann man das auch so machen, dass man dem Algorithmus sagt, dass er an eine Zeile springen soll, die gar nicht existiert. Dann terminiert er auch
Im englischen Wikipedia steht eine Lösung mit einer Regel weniger. Dort wird jede 0 direkt als Marke weiterverwendet.
1.) 0(leeres Wort) -> 0#; 1(leeres Wort) -> 1#;
2.) 0# -> ##0; 1# -> ##I1; I# -> #I; 0I -> I0; 1I -> I1;
3.) (leeres Wort)# -> (leeres Wort); 0(leeres Wort) -> (leeres Wort); 1(leeres Wort) -> (leeres Wort)
Die # geben an, in welcher Potenz die derzeitige Stelle steht. Pro # werden zwei neue # generiert und zusätzlich, wenn es sich um eine 1 handelte, ein Strich.
Für 110 sieht das folgendermaßen aus:
0.) 110
1.) 110#
2.) 11##0; 1##I1#0; 1##I##I10; 1###I#I10; 1####II10; ##I1###II10; ##I##I1##II10; ##I##I##I1#II10; ##I##I##I##I1II10; ... ; ########IIII1II10; ########IIIIII110;
3.) ...; IIIIII110; ...; IIIIII;
Gute Idee, aber
2.) 11##0; 1##I1#0
funktioniert so nicht, weil Regel 1.) früher greift. Also passiert stattdessen
2.) 11##0; 11##0#
Ich denke, das kann man irgendwie reparieren...
Ich hatte mich jetzt nur kurz mit Markov-Tabellen auseinandergesetzt. Dachte das ist so, dass erst alle Regeln von 1.) erschöpfend angewandt werden, dann alle von 2.) und am Ende alle von 3.).
OMG, das isst doch vertrackter, als es aussieht. Deshalb nochmal ausführlicher:
Aus 110 wird via 1. und 2. -| -| - (Leerzeichen nur zwecks Lesbarkeit).
Dann greift ein paar mal 3. und schiebt die - nach links:
=> - -|| | -
=> - -|| -||
=> - -| -|| ||
=> - - -|| || ||
Formal gilt bei Regel 3 folgende Konstante: Jedes | hat den Wert
und die Summe dieser Werte ist konstant. Anfangs (nach 1. und 2.) entspricht diese Summe der Binärdarstellung (hier: 2²+2¹), und nach allen 3. ist sie nur noch die Zahl der | [q.e.d.]