 information, i.e., H(X)(()xp(x)I(x)p(x)lop(x). (7.4) Thus, the entropy (or strictly [H(x)] for a rounded integer) provides the minimum num- ber of bits required on average to describe the source events. In algorithmic information theory, the Kolmogorov complexity (or algorithmic entropy) represents the minimum UTM program size required to describe the source event X, without any knowledge of its probability p(x). Thus, complexity measures the absolute information contents of an individual event from a source, in contrast to Shannon entropy, which measures the average information contents of the whole event source. In the following, I shall establish that the average minimum size of programs describing a random source, (K(x)) X, is approximately equal to the source's entropy H(X). As can be authoritatively stated:13 It is an amazing fact that the expected length of the shortest binary computer description of a random variable is approximately equal to its [source] entropy. Thus, the shortest computer description acts as a universal code, which is uniformly good for all probability distributions. In this sense, algorithmic complexity is a conceptual precursor of entropy. 13 T.M. Cover and J.A. Thomas, Elements of information theory (New York: John Wiley & Sons, 1991). Algorithmic entropy and Kolmogorov complexity The following examples will convey a practical understanding of Kolmogorov com- plexity and its close relation to Shannon entropy, as events become increasingly random: Example 7.6 Consider the event sequence X = ABABABABAB from the source alphabet Xn with X = {A, B, C, , Z}. If we want to save this sequence for a permanent archive, we might just write down ABABABABAB on a piece of paper. But if the sequence had 1000 characters with 500 repeats of AB, we would not do that. Instead, we would write down "repeat AB 500 times." It then takes only 19 alphanumeric characters (including spaces) instead of 1000, to describe X exactly. The statement q(x) = repeat AB 500 times (7.5) is thus a Turing machine program