In Kolmogorov's $ K(s) \leq |s| + c $, why is $c$ +ve?

Question

Kolmogorov said "It seems natural to call a chain random if it cannot be written down in a more condensed form, i.e., if the shortest program for generating it is as long as the chain itself. " So for example (in bits & bytes):-

$$ K(\text{a thousand zeros}) \approx \log_2(1000) \text{bits} $$

$$ K(\text{Shakespeare's works}) \approx \text{1 MB} $$

$$ K(\text{\dev\random}) = \text{| \dev\random |} $$

The second being so as his works will compress to about a megabyte. Both of the first two examples have the Kolmogorov complexity much less than the original ('chain') itself. The last example is Kolmogorov random and thus equal to the chain length.

So why is $c$ considered positive and not negative, or zero?

---

I'm refering to the old \dev\random when it was truly random and not as recently crippled to \dev\urandom.

Answer 1

If we had $K(s) \le |s|-1$ (for example), then that would mean that every string can be compressed to a strictly shorter one. It is known that this is impossible: see No compression algorithm can compress all input messages?.

See also https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_applications, https://cs.stackexchange.com/a/7533/755.

Therefore, there exists a string $s$ for which $K(s) \ge |s|$. In other words, there is no constant $c<0$ such that $K(s) \le |s|+c$ holds for all $s$.