4
$\begingroup$

Is it true that for all strings of a given length (for any alphabet with more than one symbol), at least one has a Kolmogorov complexity equal to its length?

If the answer is Yes, is there a proof of that?

Background

As an uncompressed string has a one-to-one relationship with a compressed one, and the number of compressed strings is less, by the pigeon hole principle there will be some uncompressed strings which do not have compressed versions. Hence, it seems that there are always strings whose complexity is the same as (or greater than) their length.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

It depends on the universal machine. Consider length 0, the empty string could have complexity 455, say.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ And we can even have universal machines relative to which no string has complexity equal to its length. (Just take a universal machine $U$ and define $V$ by letting $V(01\tau)=U(\tau)$ for all $\tau$ and $V(1\tau)=U(\tau)$ whenever $|U(\tau)|=|\tau|+2$.) $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 12, 2014 at 4:37
  • $\begingroup$ Nice construction $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Mar 12, 2014 at 4:59
  • $\begingroup$ @BjørnKjos-Hanssen Please see the background, which I state above. $\endgroup$
    – ARi
    Commented Mar 13, 2014 at 4:51
  • 3
    $\begingroup$ @ARi Your argument is indeed the proof that there is always a string whose complexity is greater than or equal to its length. But the complexity of a string can be greater than its length (though only by an additive constant depending on the choice of universal machine). $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 13, 2014 at 12:37
  • $\begingroup$ @DenisHirshfeldt Correct I have added this fact to the argument $\endgroup$
    – ARi
    Commented Nov 28, 2015 at 14:05

Not the answer you're looking for? Browse other questions tagged .