Quantifizierung der Nicht-Zufälligkeit eines spezialisierten Zufallsgenerators?

Als Folge von Rices Theorem gibt es keine Möglichkeit zu sagen, was ist was.

Beweis: Sei L die Ausgabe des normalen RNG. Sei L 'L, aber mit allen Folgen der Länge & gt; = 3 entfernt. Einige TMs erkennen L ', manche jedoch nicht. Daher ist es nach dem Satz von Rice nicht entscheidbar, zu bestimmen, ob ein TM L 'akzeptiert.

Wie andere bemerkt haben, können Sie vielleicht eine Aussage machen wie "Es hat für N Schritte gelaufen, ohne dreimal zu wiederholen", aber Sie können niemals den Sprung zu "es wird nie wiederholen eine Ziffer dreimal. " Geeigneterweise gibt es mindestens eine Maschine, für die Sie nicht bestimmen können, ob sie dieses Kriterium erfüllt oder nicht.

Vorbehalt: Wenn Sie einen wirklich zufälligen Generator (z. B. Kernzerfall) hätten, wäre es möglich, dass der Satz von Rice nicht gilt. Meine Intuition ist, dass das Theorem immer noch für diese Maschinen gilt, aber ich habe es noch nie diskutiert.

BEARBEITEN : ein sekundärer Beweis. Angenommen, P(X) ermittelt mit hoher Wahrscheinlichkeit, ob X L' akzeptiert oder nicht. Wir können eine (unendliche Anzahl von) Programmen F wie:

P kann das Verhalten von F(P) nicht ermitteln. Außerdem sagt P das Verhalten von G korrekt voraus. Wir können konstruieren:

Also muss es für jeden guten Fall mindestens einen schlechten Fall geben.

Wenn S durch Ablehnen von R definiert ist, dann ist eine von S erzeugte Sequenz eine Untersequenz der Sequenz, die von R erzeugt wird. Wenn Sie beispielsweise eine einfache Zufallsvariable X mit der gleichen Wahrscheinlichkeit wie 1 oder 0 verwenden, müssten Sie:

Der einzige wirkliche Weg, diese beiden zu unterscheiden, besteht darin, nach Streifen zu suchen. Wenn Sie Binärzahlen erzeugen, dann sind Streifen unglaublich häufig (so sehr, dass man fast immer zwischen einer zufälligen 100-stelligen Sequenz und einer unterscheiden kann, die ein Schüler schreibt, wenn er versucht, zufällig zu sein). Wenn die Zahlen von [0,1] gleichmäßig übernommen werden, sind Streifen weit weniger verbreitet.

Es ist eine einfache Übung in der Wahrscheinlichkeit, die Wahrscheinlichkeit zu berechnen, dass drei aufeinanderfolgende Zahlen gleich sind, sobald Sie die Verteilung kennen, oder sogar die erwartete Anzahl von Zahlen, bis die Wahrscheinlichkeit von drei aufeinanderfolgenden gleichen Zahlen größer ist als p für Ihre Lieblingswahl von p .

Wahrscheinlich verwenden Sie ENT ( Ссылка )