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?
-
$\begingroup$ compression algorithms are taken as rough approximations of Kolmogorov complexity. KC as strictly defined uses TMs and other languages are within a constant factor of a TM. the first N ints can be enumerated by a TM of constant size. $\endgroup$– vznJan 10, 2014 at 4:45
-
1$\begingroup$ Are you looking for the Kolmogorov complexity of the sequence $1, \dots, N$ or the sequence of Kolmogorov complexities $K(1), \dots, K(N)$? $\endgroup$– David RicherbyJan 12, 2014 at 16:05
2 Answers
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)$.
-
$\begingroup$ This presumes that the question is looking for $K([[n]])$, but I think the interesting reading of the question - as mentioned in David's comment - is to ask for asymptotic estimates of $\sum_{i=1}^nK(i)$. as a function of $n$. $\endgroup$ Jan 12, 2014 at 23:47
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)$).