8
$\begingroup$

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?

$\endgroup$
  • $\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$ – vzn Jan 10 '14 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 Richerby Jan 12 '14 at 16:05
6
$\begingroup$

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)$.

$\endgroup$
  • $\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$ – Steven Stadnicki Jan 12 '14 at 23:47
2
$\begingroup$

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)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.