 the demonstration, we needed to consider "bits" and "strings." But we could also consider X* as a random source of strings X with probability p(x) and entropy H(X*). Thus, we have (K(x)) 2 H(X*) as the asymptotic limit, which eliminates the need to refer to a "per-bit" average complexity. The above result, thus, establishes the truly amazing and quite elegant property according to which Kolmogorov complexity and Shannon's entropy give very similar measures of information. Such an asymptotic relationship holds despite the profound conceptual difference existing between algorithmic and Shannon information theories. Exercises 7.1 (M): Use a Turing machine to add the two numbers i = 4 and j = 2, using the action table in Table 7.3. 7.2 (B): Use a Turing machine to subtract the two numbers i = 4 and j = 3, using the action table in Table 7.5. 7.3 (T): Solve Exercise 7.2 first. Then complete the subtraction algorithm by introduc- ing a new TM state aiming to clean up the useless 0 in the output tape sequence, in the general case with i > j. 7.4 (T): Define, for a Turing machine, an algorithm Comp, and a corresponding action table, whose task is to compare two integers i, j, and whose output is either Comp(i > j) = 0 or Comp(i < j) = 1. Clue: begin the analysis by solving Exer- cise 7.2 first. Algorithmic entropy and Kolmogorov complexity 7.5 (T): Determine the number of division or subtraction operations required to convert the unary number N1 = 11_1111_1111_1111_0 into its decimal (N10) representation. Notes: (a) separators have been introduced in the definition of N1 for the sake of reading clarity; (b) the convention of the unary representation chosen here is 1 10 = 10. 7.6 (T): Show how a Turing machine can convert the binary number M2 = 1001 into its unary (M1) representation. Note: use the convention for the unary repre- sentation 110 = 10. Information coding This chapter is about coding information, which is the art of packaging and formatting information into meaningful codewords. Such codewords are meant to b