Wirklich Zufallsgenerator: Turing berechenbar?

39

Ich suche eine endgültige Antwort darauf, ob die Erzeugung von "wirklich zufälligen" Zahlen für Turing berechenbar ist oder nicht. Ich weiß nicht, wie ich das genau ausdrücken soll. Diese StackExchange-Frage zum Thema "Effiziente Algorithmen für die Zufallsgenerierung" kommt der Beantwortung meiner Frage sehr nahe. Charles Stewart sagt in seiner Antwort: "Es kann keine [Martin-Löf-Zufälligkeit] von einer Maschine erzeugt werden." Ross Snider sagt: "Jeder deterministische Prozess (wie Turing / Register Machines) kann keine 'philosophischen' oder 'wahren' Zufallszahlen erzeugen." Gibt es eine klare und akzeptierte Vorstellung davon, was einen echten Zufallsgenerator ausmacht? Und wenn ja, ist es bekannt, dass es von einer Turing-Maschine nicht berechnet werden kann?

Vielleicht würde es ausreichen, mich auf die einschlägige Literatur zu verweisen. Vielen Dank für jede Hilfe, die Sie zur Verfügung stellen können!

Bearbeiten. Vielen Dank an Ian und Aaron für die sachkundigen Antworten! Ich bin in diesem Bereich relativ ungeschult und dankbar für die Unterstützung. Wenn ich die Frage in diesem Anhang ein wenig erweitern darf: Kann ein TM mit Zugriff auf eine reine Zufallsquelle (ein Orakel?) Eine Funktion berechnen, die ein klassisches TM nicht kann?

Joseph O'Rourke
quelle
1
Es hilft, wenn Sie zuerst die Definition von "wirklich zufällig" betrachten.
MS Dousti

Antworten:

52

Ich nehme ziemlich spät an der Diskussion teil, werde aber versuchen, einige Fragen zu beantworten, die zuvor gestellt wurden.

Zunächst ist es, wie von Aaron Sterling festgestellt, wichtig, zunächst zu entscheiden, was wir unter "wirklich zufälligen" Zahlen verstehen, und zwar insbesondere dann, wenn wir die Dinge unter dem Gesichtspunkt der Komplexität der Berechnungen oder der Berechenbarkeit betrachten.

Lassen Sie mich jedoch argumentieren , dass in der Komplexitätstheorie, die Menschen vor allem interessiert sind Pseudo -randomness und Pseudo -random Generatoren, dh Funktionen von Strings in Strings , so dass die Verteilung der Ausgangssequenzen kann nicht abgesehen von der gleichmäßigen Verteilung erzählt wird durch ein effizientes Verfahren (wo mehrere Bedeutungen von effizient in Betracht gezogen werden können, z. B. Polyzeit berechenbare, polynomgroße Schaltungen usw.). Es ist ein wunderschönes und sehr aktives Forschungsgebiet, aber ich denke, die meisten Leute würden zustimmen, dass die Objekte, die es untersucht, nicht wirklich zufällig sind, es ist genug, dass sie nur zufällig aussehen (daher der Begriff "Pseudo").

In der Berechenbarkeitstheorie hat sich ein Konsens zu einem guten Begriff der "wahren Zufälligkeit" herauskristallisiert, und es hat sich tatsächlich der Begriff der Martin-Löf-Zufälligkeit durchgesetzt (andere wurden vorgeschlagen und sind interessant zu studieren, aber nicht alle die netten Eigenschaften, die Martin-Löf zufällig hat). Zur Vereinfachung betrachten wir die Zufälligkeit für unendliche binäre Sequenzen (andere Objekte wie Funktionen von Zeichenfolgen zu Zeichenfolgen können mit einer solchen Sequenz leicht codiert werden).

α

1/20α
kwk,0wk,1Ukwk,i2kG=kUk0α

Diese Definition mag technisch erscheinen, wird jedoch aus mehreren Gründen allgemein als die richtige angesehen:

  • es ist effektiv genug, dh seine Definition beinhaltet berechenbare Prozesse
  • Es ist stark genug: Jede "fast sichere" Eigenschaft, die Sie in einem Wahrscheinlichkeitstheorie-Lehrbuch finden (Gesetz der großen Zahlen, Gesetz des iterierten Logarithmus usw.), kann durch einen Martin-Löf-Test getestet werden (obwohl dies manchmal schwer zu beweisen ist).
  • Es wurde unabhängig von mehreren Personen unter Verwendung unterschiedlicher Definitionen vorgeschlagen (insbesondere die Levin-Chaitin-Definition unter Verwendung der Kolmogorov-Komplexität). und die Tatsache, dass sie alle zu demselben Konzept führen, ist ein Hinweis darauf, dass es der richtige Begriff sein sollte (ein bisschen wie der Begriff der berechenbaren Funktion, der über Turing-Maschinen, rekursive Funktionen, Lambda-Kalkül usw. definiert werden kann).
  • Die mathematische Theorie dahinter ist sehr schön! Siehe die drei ausgezeichneten Bücher Eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen (Li und Vitanyi), Algorithmische Zufälligkeit und Komplexität (Downey und Hirschfeldt), Rechenbarkeit und Zufälligkeit (Nies).

Wie sieht eine Martin-Löf-Zufallsfolge aus? Nehmen Sie eine perfekt ausbalancierte Münze und werfen Sie sie um. Schreiben Sie bei jedem Flip eine 0 für Kopf und eine 1 für Zahl. Fahren Sie bis zum Ende der Zeit fort. So sieht eine Martin-Löf-Sequenz aus :-)

ααααkakαk2kUkα

αβαnnO(1)βnα


Ok, jetzt der "Edit" -Teil von Josephs Frage: Kann ein TM mit Zugriff auf eine reine Zufallsquelle (ein Orakel?) Eine Funktion berechnen, die ein klassisches TM nicht kann?

f:NNfnn

ffnnfϵ>0σσfσ

LaurentBienvenu
quelle
8
Was für eine schöne Antwort.
Suresh Venkat
1
Ich bin sehr dankbar für die Klarheit Ihrer detaillierten Antwort auf diese (für mich!) Verwickelte Frage. Vielen Dank!
Joseph O'Rourke
12

Es ist (vielleicht) zu unterscheiden zwischen "Turing berechenbar" und "effektiv berechenbar", um Ihre Frage zu beantworten. Wenn man "zufälligen Prozess" als "einen Prozess definiert, der nicht vorhergesagt werden kann, unabhängig davon, über welche Ressourcen wir verfügen", und man "deterministischen Prozess" als "vorhersagbaren Prozess" definiert, wenn man den Input und den Zugriff auf (möglicherweise viele) Ressourcen voraussetzt, "Dann kann keine berechenbare Turing-Funktion zufällig sein, denn wenn wir die Turing-Maschine kennen und simulieren würden, könnten wir immer das Ergebnis des nächsten" Experiments "des Prozesses vorhersagen.

In diesem Rahmen kann ein Martin-Lof-Test als deterministischer Prozess angesehen werden, und die Definition einer zufälligen Sequenz ist genau eine Sequenz, deren Verhalten von keinem Martin-Lof-Test / Turing-berechenbaren / deterministischen Prozess vorhergesagt wird.

Dies wirft jedoch die Frage auf: "Ist eine Zufallsfolge im wirklichen Leben effektiv berechenbar?" Tatsächlich gibt es hier eine Branche. Es gibt veröffentlichte CDs mit Milliarden zufälliger (?) Bits, die zur Durchführung von Computersimulationen physikalischer Systeme usw. verwendet werden. Diese CDs garantieren, dass ihre Bitsequenzen eine Reihe von Martin-Lof-Tests bestehen. Das Buch The Drunkard's Walk: Wie Zufälligkeit unser Leben regiert, gibt eine Pop-Science-Erklärung zu diesem Thema.

Irrelevanter Punkt: Ich genieße Ihre Kolumne. :-)

Aaron Sterling
quelle
11

Intuitiv bedeutet "zufällig" "unvorhersehbar", und jede von einer Turing-Maschine erzeugte Sequenz kann durch Ausführen der Maschine vorhergesagt werden, so dass Turing-Maschinen keine "wirklich zufälligen" Zahlen erzeugen können. Es gibt eine Reihe formaler Definitionen von Zufallsfolgen (Zufälligkeit ist nur dann wirklich sinnvoll, wenn die Länge einer Zeichenfolge unendlich ist), die alle im Wesentlichen gleichwertig sind. Die vielleicht natürlichsten davon sind die Martin-Lof-Zufälligkeit, dh eine Sequenz besteht alle möglichen berechenbaren statistischen Tests auf Stochastizität, und die Chaitin-Zufälligkeit, dh alle anfänglichen Teilsequenzen sind inkompressibel (genauer gesagt, sie weisen eine hohe Kolmogorov-Komplexität auf). In diesen beiden Definitionen ist es nicht möglich, zufällige Sequenzen zu erzeugen und sie zu erkennen. Siehe das Buch "Information und Zufälligkeit:

Ian
quelle
Link zur Buchung hier: amazon.com/…
Suresh Venkat
Danke, Ian & Suresh, ich hole das Buch aus unserer Bibliothek!
Joseph O'Rourke
Ein weiteres großartiges Buch ist Nies '"Berechenbarkeit und Zufälligkeit".
Diego de Estrada
11

Jeder, der arithmetische Methoden zur Erzeugung von Zufallszahlen in Betracht zieht, befindet sich natürlich in einem Zustand der Sünde. Denn wie bereits mehrfach erwähnt, gibt es keine Zufallszahl - es gibt nur Methoden zur Erzeugung von Zufallszahlen, und ein strenges Rechenverfahren ist natürlich keine solche Methode. - John von Neumann

Jeffε
quelle
Ha! Tolles Zitat, Jeff! Und mit einem inhaltlichen Punkt.
Joseph O'Rourke
7

Es scheint, als hätte niemand auf Ihren Nachtrag geantwortet, also werde ich es versuchen:

Wenn ich die Frage in diesem Anhang ein wenig erweitern darf: Kann ein TM mit Zugriff auf eine reine Zufallsquelle (ein Orakel?) Eine Funktion berechnen, die ein klassisches TM nicht kann?

Ich werde versuchen, die Frage zu präzisieren und sie dann zu beantworten. (Meine Version entspricht jedoch möglicherweise nicht Ihren Vorstellungen. Lassen Sie es mich wissen, wenn dies nicht der Fall ist.)

Wir haben ein deterministisches TM mit Zugriff auf einen Zufallszahlengenerator. Dieses TM berechnet nun eine Funktion (eine tatsächliche Funktion, dh eine deterministische Abbildung von einem Eingaberaum zu einem Ausgaberaum), wobei der Zufallszahlengenerator auf irgendeine Weise verwendet wird.

Darf das TM mit Zugriff auf die Zufälligkeit also Fehler machen? Wenn nicht, muss der DTM die richtige Antwort geben, unabhängig davon, welche zufälligen Bits er geliefert hat. In diesem Fall sind die Zufallsbits nicht erforderlich, da Sie die Zufallszeichenfolge einfach als 00000 annehmen könnten ...

fi(x,r)fir

Robin Kothari
quelle
Ich finde das aufschlussreich: "Wenn nicht, dann muss der DTM die richtige Antwort geben, egal welche zufälligen Bits er geliefert hat." Vielen Dank!
Joseph O'Rourke
Eigentlich verstehe ich das nicht. Sie scheinen vorzuschlagen, dass P = ZPP ist oder dass ein randomisierter Algorithmus mit Null-Fehler (zum Beispiel ein Las Vegas-Algorithmus) deterministisch sein muss?
Suresh Venkat
Bei einem DTM mit Oracle-Zugriff, der eine Sprache festlegt, habe ich angenommen, dass der DTM nach einer begrenzten Zeitspanne anhält. In diesem Fall können wir das Orakel loswerden. Für Null-Fehler ersetzen wir es einfach durch 0000 ..., und für jeden anderen Zweck kann man über alle zufälligen Zeichenfolgen mit endlicher Länge Gewalt anwenden. (Ich bin sicher, dass wahrscheinlich jemand der Meinung ist, dass Las Vegas-Algorithmen nicht wirklich Algorithmen sind, da sie nicht unbedingt enden.)
Robin Kothari
5

In Bezug auf Ihre "Bearbeitungsfrage": Es macht einen großen Unterschied, ob Sie nach der Berechenbarkeit oder Komplexität fragen. Wenn es Komplexitätsgrenzen für das TM gibt, erhalten Sie das sogenannte zufällige Orakelmodell . Wenn der TM beliebig große, aber endliche Ressourcen verwenden kann, dann befinden Sie sich in der Welt der relativen Zufälligkeit : Es gibt Zufallshierarchien von Orakeln, genau wie es Turing-Grade gibt. (Randbemerkung: Eine der (in) berühmten Kritiken von Koblitz und Menzes betraf die Verwendung des Zufalls-Orakelmodells, sodass Ihre Meta-Frage die jüngsten akademischen Debatten berührt.)

Aaron Sterling
quelle
Nur um das zu verdeutlichen: Wollte Joe ein zufälliges Orakel (das im Wesentlichen eine zufällige Hash-Funktion ist) oder nur eine Quelle der Zufälligkeit? das ist doch nicht dasselbe, oder?
Suresh Venkat
Danke, Aaron, die Erwähnung von Zufälligkeits- oder Orakelhierarchien ist nützlich.
Joseph O'Rourke
@ Suresh: Ich meinte eine Quelle der Zufälligkeit.
Joseph O'Rourke
Sie beide sind mir hier wahrscheinlich weit voraus, aber ich habe versucht zu sagen, dass die Zufälligkeit in Bezug auf einen "Bezugsrahmen" definiert werden muss, dh die Ressourcen, die zur Verfügung stehen, um Vorhersagen zu treffen. Eine "Quelle der Zufälligkeit" kann in Bezug auf eine Turing-Maschine zufällig sein, nicht jedoch in Bezug auf das Orakel des Stillstands. Ich stimme Robin Kotharis Antwort zu. Mein einziger Punkt war, dass eine "reine Quelle der Zufälligkeit" unter den gegenwärtigen Definitionen nicht zu existieren scheint, weil wir immer dagegen diagonalisieren und etwas Zufälliges erhalten könnten.
Aaron Sterling
5

Ich versuche immer noch, Ihre veränderte Frage zu verstehen, insbesondere, welche Einschränkungen Sie dem TM auferlegen. Obwohl diese Antwort möglicherweise nicht genau Ihren Wünschen entspricht, hilft sie möglicherweise, die Dinge ein wenig einzugrenzen.

Wir wissen, dass es unbedingt unmöglich ist, das Volumen eines konvexen Körpers deterministisch mit einem subexponentiellen Faktor anzunähern (dies ist ein altes Ergebnis von Bárány und Füredi ). Im Gegensatz dazu können wir mithilfe von Stichproben ein FPRAS für dieses Problem erhalten. Ist dies ein Beispiel für die Trennung, die Sie suchen?

Suresh Venkat
quelle
Dieses Ergebnis gilt für polynomielle Zeitalgorithmen, oder? Ich interpretierte die Frage des OP als eine Frage der Berechenbarkeitstheorie, nicht der Komplexitätstheorie. Womit ich meine, dass ich es so interpretiert habe, dass es bedeutet, dass die Menge der Probleme, die von einer DTM + -Zufallsquelle gelöst werden, größer ist als die, die von einer DTM gelöst werden?
Robin Kothari
Das ist möglich. Daher mein Versuch, es genauer zu konkretisieren. Auf der Ebene der Berechenbarkeit würde eine Diskrepanz die Church-Turing-These jedoch für ungültig erklären.
Suresh Venkat
Ich mag dieses Volumenbeispiel! Obwohl ich speziell nach der Berechenbarkeitstheorie gefragt habe, interessiere ich mich auch für Komplexitätsunterschiede. Ich sehe nicht ein, wie dies die CT ungültig machen könnte, da die vorherigen Antworten gezeigt haben, dass eine reine Quelle wahrer Zufälligkeit nicht berechenbar ist ...?
Joseph O'Rourke
Ich denke, wenn wir erst einmal formalisieren, was wir unter einem DTM mit Zugriff auf eine Zufallsquelle (mit Akzeptanzkriterien, Stoppwahrscheinlichkeit usw.) verstehen, sollten wir zeigen können, dass dieses Modell auch genau die rekursiven Sprachen berechnet.
Robin Kothari
True (im Bereich der ausführbaren Dateien). Aber jetzt frage ich mich: Nehmen wir an, wir konstruieren einen String, dessen i-tes Bit das Ergebnis der Ausführung der i-ten Maschine mit einer Codierung von sich selbst ist. Würde die Vorhersage dieser Zeichenfolge der Lösung des Halteproblems entsprechen, und ist diese Zeichenfolge zufällig im Sinne von Martin-Lof?
Suresh Venkat