 halting problem and the puzzling universe of Turing machines, in order to resume our focus in information theory. With what we have learnt about universal Turing machines, we are now able to broaden our appreciation of information theory with the new concept of algorithmic entropy or algorithmic complexity, or Kolmogorov complexity. It is sufficient to include in the TM program an instruction that is certain to be called regardless the input data, and in which the output state is undefined (TM certain to halt), or an instruction creating a nested loop (TM certain never to halt). 7.4 Kolmogorov complexity Kolmogorov complexity In Section 7.1, I introduced, without discussion, the definition of complexity, which I equivalently referred to as algorithmic information content, algorithmic complexity, algorithmic entropy, or Kolmogorov-Chaitin complexity. In what is called algorithmic information theory, the object variable x represents any symbol sequence from an events source X, whether random or deterministic. The underlying concept is that there must exist one, several, or an infinity of universal Turing- machine (UTM) programs, q, which are capable of outputting the sequence X, and then halt. We shall note any such programs as q(x). As mentioned earlier, the Kolmogorov complexity of X, noted K (x), is defined as the minimum size of q(x), i.e.: K(x) = min q (x) , (7.2) where the symbol stands for the program length, i.e., the number of bits defining the program. The concept of Kolmogorov complexity nicely parallels that of information in Shannon's theory. Recall from Chapter 3 that, given a source event x E X, the cor- responding information is I(x) )==logp(x). (7.3) Shannon's information provides the minimum number of bits required to describe this event. More accurately, the minimum length of the description is given by the integer [I(x)], where the symbol means the closest integer greater than or equal to I(x). As we have seen in Chapter 4, Shannon's entropy H(X) represents the statistical average of the source