I need help with a counterintuitive result that I found regarding computing Kolmogorov Complexities.
Suppose two strings, being s1:
5p$j3
and s2:
ababab
I want to compute the Kolmogorov Complexity of s1 and of s2, that is, K(s1) and K(s2).
In pseudo-code, we could have for s1:
return "5p$j3"
such as K(s1) = 14.
And also in pseudo-code, we could have for s2:
return "ababab"
such as K(s2) = 15.
It is possible to also do:
return "ab" x 3
Which would also give K(s2) = 15.
Intuitively, you would think that algorithmic complexity would be greater for s1 than s2, that, by itself, looks much more simpler, but K(s2) > K(s1) as far as I could go.
How to explain this result? Is "ababab", considering the computation of Kolmogorov Complexity, actually more algorithmically complex than "5p$j3"? Maybe there is another way to write the "ababab" string so it actually computes a lower value for K(s2)?
Thank you for your time.
It doesn't make a lot of sense to compute Kolmogorov Complexity for one specific string, because it depends on programming language. For example, we can take some random string $s$ of length $10^{100}$, some universal decompressor, and create new decompressor, that outputs $s$ if the first bit of input is $0$, otherwise drops the first bit of input and launches universal decompressor - this also will be a universal decompressor, but complexity of $s$ by it will be just $1$.
What makes more sense is to speak about asymptotic behaviour of Kolmogorov complexity. For example, Kolmogorov complexity of string $(ab)^n$ ($ab$ repeated $n$ times) is at most $\log_2 n + C$, where $C$ doesn't depend on $n$, while complexity of most strings of length $2n$ is at least $2n$ - so, if you take $n$ large enough, you will get that $(ab)^n$ is simpler than most of strings of the same length.