What is an estimation of the Kolmogorov Complexity for the first N integers?

Question

I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number 5.41126806512 has a very low complexity as it can be expressed by 17/pi. I'm also aware that, though the KC varies depending on the expression language, it is always the same up to a given constant. So, I ask: is there a way to calculate an approximation of the KC for the first N ints?

Answer 1

No, there is no general algorithm to compute a close approximation to the Kolmogorov complexity of the sequence $1,2,\dots,n$. Any candidate algorithm you come up with will have some inputs where it gives a bad answer (a poor approximation to the correct answer).

Denote by $[n]$ the binary encoding of the natural number $n$, and let $[[n]] = [1],[2],\ldots,[n]$ denote a comma-separated encoding of the sequence $1,\ldots,n$. It is not hard to check that $|K([n]) - K([[n]])| = O(1)$. Since computing $K([n])$ is undecidable, it follows that computing a good approximation to $K([[n]])$ is also undecidable.

Furthermore, it is known that for "most" integers $n$, $K([n]) = \Theta(\log n)$. So for "most" integers $n$, $K([[n]]) = \Theta(\log n)$.

Answer 2

One way of expressing the statement 'almost all numbers are maximally random' is as the assertion that $\sum_{i=1}^N K(i) \in\Theta(N\lg N)$. For convenience's sake, set $N=2^k$ and consider just the portion of the sum from $2^{k-1}$ to $2^k$; then for each $c$ we have that the number of numbers of this length with complexity $\geq k-c$ is $2^{k-1}-2^{k-c}$ (see http://en.wikipedia.org/wiki/Kolmogorov_complexity for some details of this), so we can split the sum into the sum of the '$c$-incompressible' numbers and the compressible numbers, with the former contributing at least $(1-2^{1-c})2^{k-1}(k-c)$ to the sum. A bit more massage should be enough to get you a constant of the form $1-o(1)$ in front (i.e., a sum of $N\lg N-o(N\lg N)$).