Entropy/connections/entropy example 5

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

\[ B=0,1,\,00,01,10,11,\,000,001,010,011,100,101,110,111,\,0000,0001\dots \]

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 \(B\) should not allow for any compression. On the other hand, since it can be completely determined in a finite set of instructions (as it is done above), its [[Kolmogorov complexity]] is zero. This phenomenon follows from the fact that the Compression Theorem takes into account only the frequency-based data compression codes, while Kolmogorov complexity allows 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 coded has measure zero.