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

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 ?

Nein, es gibt keinen allgemeinen Algorithmus, um eine enge Annäherung an die Kolmogorov-Komplexität der Sequenz zu berechnen $1,2,\dots,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],\ldots,[n]$ bezeichnen eine durch Kommas getrennte Codierung der Sequenz $1,\ldots,n$. Es ist nicht schwer, das zu überprüfen$|K([n]) - K([[n]])| = O(1)$. Seit dem Rechnen$K([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]) = \Theta(\log n)$. Also für "die meisten" ganzen Zahlen$n$, $K([[n]]) = \Theta(\log n)$.

Eine Möglichkeit, die Aussage "fast alle Zahlen sind maximal zufällig" auszudrücken, ist die Behauptung, dass $\sum_{i=1}^N K(i) \in\Theta(N\lg N)$. Zur Vereinfachung einstellen$N=2^k$ und betrachte nur den Teil der Summe aus $2^{k-1}$ zu $2^k$;; dann für jeden$c$ wir haben das die Anzahl der Zahlen dieser Länge mit Komplexität $\geq k-c$ ist $2^{k-1}-2^{k-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-2^{1-c})2^{k-1}(k-c)$zur Summe. Ein bisschen mehr Massage sollte ausreichen, um eine konstante Form zu erhalten$1-o(1)$ vor (dh eine Summe von $N\lg N-o(N\lg N)$).