Entropie Umpacken

Question

Ich habe eine konzeptionelle Idee für eine Maschine geworfen (wie in einer Turing-Maschine) und Ich frage mich, ob irgendwelche Arbeit zu diesem oder verwandten Themen getan wurde.

Die Idee ist eine Maschine, die einen Entropiestrom nimmt und zufällige Symbole in jedem Bereich ohne Verlust der Entropie ausgibt.

Ich werde großartig, dass ein weit von rigorosen Beschreibung ist so werde ich ein Beispiel: Sagen wir, ich einen Generator von Zufalls Symbole im Bereich von 1-n haben und ich möchte für ein Zeichen bitten können, in jeden gegebenen Bereich, zuerst 1 bis 12 und dann 1 bis 1234. (Um es praktikabel zu halten, werde ich nur deterministische Maschinen betrachten, bei denen bei gleichem Eingabestrom und gleichen Anforderungen immer die gleiche Ausgabe ausgegeben wird.) Eine notwendige Einschränkung besteht darin, dass die Ausgabe mindestens so viel Entropie enthält wie die Eingabe. Die Einschränkung, die mich am meisten interessiert, ist jedoch, dass die Maschine nur soviel Entropie einliest, wie sie ausspuckt.

z. Wenn nach Token im Bereich von 1 bis S1, S2, S3, ... Sm gefragt wird, würde es nur ceiling(sum(i = 1 to m, log(Si))/log(n)) Input-Tokens verbrauchen.

This question fragt nach, wie diese Konvertierung durchgeführt wird, während die erste Einschränkung erfüllt wird, aber sehr schlecht auf der zweiten.

Answer 1

Okay, ich bin mir immer noch nicht sicher, ob ich dem folge was du willst. Es klingt wie Sie eine Funktion

f wollen: Ich → O

wo die Eingänge sind eine stark zufällig (gleichmäßige Verteilung usw.) Folge von Symbolen auf einem Alphabet I = {1 .. n}. (Also eine Reihe von zufälligen natürlichen Zahlen ≤ n.) Die Ausgänge sind eine andere Sequenz auf O = {1 .. m} und Sie wollen, dass diese Sequenz so viel Entropie wie die Eingänge haben.

Okay, wenn ich das Recht habe, zuerst aus, wenn m < n, können Sie nicht. Wenn m dann m < lg n, so ist die Entropie der Menge der Ausgangssymbole kleiner.

Wenn m ≥ n, dann können Sie es trivialerweise tun, indem Sie einfach das von i ^th Elemente Auswahl von {1 .. m}. Die Entropie wird gleich sein, da die Anzahl der möglichen Ausgabesymbole gleich ist. Sie werden nicht "zufällig" in dem Sinne sein, dass sie gleichmäßig über die gesamte Menge verteilt sind {1 .. m}, obwohl notwendigerweise (Schubladprinzip) einige Symbole überhaupt nicht ausgewählt werden.

Wenn Sie andererseits mit einer zufälligen Sequenz auf {1 .. m} zufrieden sind, können Sie dies tun, indem Sie einen geeigneten Pseudozufallszahlengenerator mit Ihrer Eingabe aus der zufälligen Quelle auswählen als ein Samen.

Answer 2

Mein aktueller Pass auf es:

Durch das Hinzufügen der folgende Einschränkung: Sie wissen im Voraus, was die Reihenfolge der Bereiche ist {S1, S2, S3, ..., Sn}, als mit einer Basis Übersetzung mit nicht konstante Basis funktionieren könnte:

1. Finden Sp = S1 * S2 * S3 * ... * Sn
2. Extract m=cealing(log(Sp)/log(n)) Begriffe aus dem Eingang {R1, R2, R3, ..., Rm}
3. Finden X = R1 + R2*n + R3*n^2 + ... + Rm*n^(m-1)
4. Reform X als O1 + S1*O2 + S1*S2*O3 + ... Sn*On + x wo 1 <= Oi <= Si

Dies könnte zu einer Lösung zu reformierenden sein, die durch Drücken x zurück in den Eingangsstrom zu einem Zeitpunkt für einen Wert arbeitet. Allerdings kann ich mich selbst nicht davon überzeugen, dass selbst die bekannten Output-Range-Form so klingt ...