Ich wäre mehr als dankbar, wenn jemand mir erklären könnte, wie Kolmogorov Komplexität mit Zufälligkeit und zufälligen Eingaben verbunden ist.Kolmogorov Komplexität
Eine andere Sache, die ich nicht verstehen kann - wir wissen, dass Berechnung Kolmogorov Komplexität einer gegebenen Eingabe X ist nicht entscheidbar. Wie kann es ein Maß für Zufälligkeit sein?
dank
Kolmogorov zufällig eine bestimmte Definition des vagen intuitive Konzept der ‚zufällig‘ - die andere Definition sind Sie sich beziehen, wenn Sie Beziehung zu fragen (als Referenz http://en.wikipedia.org/wiki/Random_number)?
Ich folge Ihrem Gedankenmuster nicht in der Frage, warum man in der Lage sein müsste, im allgemeinen Fall zu bestimmen, welche Strings von Kolmogorov zufällig sind, damit das Konzept gut definiert ist. Können Sie näher erläutern, was Ihnen Probleme bereitet? Lassen Sie mich, wenn nichts anderes, auf das Halteproblem hinweisen - sicherlich ist das Konzept eines Programmstopps klar definiert, obwohl es im allgemeinen Fall keinen Algorithmus geben kann, um zu bestimmen, ob ein bestimmtes Programm die Eigenschaft aufweist.
Sie sollten anders herum denken. Wenn etwas nicht zufällig ist, bedeutet es, dass es einige Gesetz folgt, und dieses Gesetz kann eine einfachere Beschreibung der Informationen geben. Denken Sie an zip: Statt der Datei geben Sie eine Prozedur, um die Datei zu erzeugen, die normalerweise kompakter als die Quelldatei ist. Dies ist möglich, weil die Quelldatei eine Reihenfolge enthielt: Wenn die Quelldatei eine zufällige Folge von Zeichen wäre, wäre keine Komprimierung möglich gewesen.
Wenn Sie an diesem Thema interessiert sind, empfehle ich "Computability and Randomness" von Andre 'Nies, Oxford Logic Guides n.51.
Danke, die zweite half wirklich meine Gedanken ein wenig zu beheben. Aber ich verstehe immer noch nicht, wie Kolmogorov mit der Charakterisierung einer zufälligen Reihenfolge verwandt ist. Ist das eine Art von Bewertung/Messung? Noch etwas kam mir in den Sinn. Wenn wir nicht feststellen können, ob eine Zahl wirklich eine Zufallszahl ist, wie können wir Zufallszahlen erzeugen? – RanZilber