View source for Entropy/connections between different meanings of entropy/entropy example 5

Consider the infinite string obtained by concatenating consecutively all words of length 1, then of length 2, etc, each time ordered lexicographically:

:<math>
B=0,1,\,00,01,10,11,\,000,001,010,011,100,101,110,111,\,0000,0001\dots
</math>

It is not hard to see that this string generates by frequencies the uniform measure, whose Kolmogorov-Sinai entropy equals 1. So, according to the assertion of the Compression Theorem, <math>B</math> should not allow for any compression. On the other hand, since <math>B</math> can be completely determined by a finite set of instructions (as is done above), its [[Kolmogorov complexity]] is zero. This phenomenon follows from the fact that the Compression Theorem takes into account only frequency-based data compression codes, while Kolmogorov complexity allows one to use any algorithmic regularity in the structure of the message. Nevertheless, the Compression Theorem says that the collection of messages with regularities undetected by frequency-based algorithms has measure zero.