Was ist eine Schätzung der Kolmogorov-Komplexität für die ersten N ganzen Zahlen?

9

Ich bin mir bewusst, dass einige Ints höhere oder niedrigere Kolmogorov-Komplexitäten haben. Zum Beispiel hat die Zahl 5.41126806512eine sehr geringe Komplexität, wie sie durch ausgedrückt werden kann 17/pi. Mir ist auch bewusst, dass der KC, obwohl er je nach Ausdruckssprache variiert, bis zu einer bestimmten Konstante immer derselbe ist. Ich frage also: Gibt es eine Möglichkeit, eine Näherung des KC für die ersten N Ints zu berechnen ?

Viclib
quelle
Komprimierungsalgorithmen werden als grobe Annäherungen an die Komplexität von Kolmogorov angesehen. KC verwendet streng definierte TMs und andere Sprachen liegen innerhalb eines konstanten Faktors eines TM. Die ersten N Ints können durch ein TM konstanter Größe aufgezählt werden.
vzn
1
Suchen Sie nach der Kolmogorov-Komplexität der Sequenz oder der Sequenz der Kolmogorov-Komplexität ? 1,,N.K(1),,K(N)
David Richerby

Antworten:

7

Nein, es gibt keinen allgemeinen Algorithmus, um eine enge Annäherung an die Kolmogorov-Komplexität der Sequenz zu berechnen 1,2,,n. Jeder Kandidatenalgorithmus, den Sie entwickeln, hat einige Eingaben, bei denen er eine schlechte Antwort gibt (eine schlechte Annäherung an die richtige Antwort).

Bezeichnen mit [n]] die binäre Codierung der natürlichen Zahl n, und lass [[n]]]]=[1]],[2]],,[n]] bezeichnen eine durch Kommas getrennte Codierung der Sequenz 1,,n. Es ist nicht schwer, das zu überprüfen|K.([n]])- -K.([[n]]]])|=Ö(1). Seit dem RechnenK.([n]]) ist unentscheidbar, folgt daraus, dass die Berechnung einer guten Annäherung an K.([[n]]]]) ist auch unentscheidbar.

Darüber hinaus ist bekannt, dass für "die meisten" ganzen Zahlen n, K.([n]])=Θ(Logn). Also für "die meisten" ganzen Zahlenn, K.([[n]]]])=Θ(Logn).

Yuval Filmus
quelle
Dies setzt voraus, dass die Frage gesucht wird K.([[n]]]]), aber ich denke, die interessante Lektüre der Frage - wie in Davids Kommentar erwähnt - besteht darin, nach asymptotischen Schätzungen von zu fragen ich=1nK.(ich). als Funktion vonn.
Steven Stadnicki
2

Eine Möglichkeit, die Aussage "fast alle Zahlen sind maximal zufällig" auszudrücken, ist die Behauptung, dass ich=1N.K.(ich)Θ(N.lgN.). Zur Vereinfachung einstellenN.=2k und betrachte nur den Teil der Summe aus 2k- -1 zu 2k;; dann für jedenc wir haben das die Anzahl der Zahlen dieser Länge mit Komplexität k- -c ist 2k- -1- -2k- -c(Siehe http://en.wikipedia.org/wiki/Kolmogorov_complexity für einige Details dazu), damit wir die Summe in die Summe der 'c-inkompressible 'Zahlen und die komprimierbaren Zahlen, wobei die ersteren zumindest dazu beitragen (1- -21- -c)2k- -1(k- -c)zur Summe. Ein bisschen mehr Massage sollte ausreichen, um eine konstante Form zu erhalten1- -Ö(1) vor (dh eine Summe von N.lgN.- -Ö(N.lgN.)).

Steven Stadnicki
quelle