y of encoding this instruction is: Convert n into a binary number of log n bits (strictly, [log2n]); Form a string m, where the bits are repeated twice; Append a delimiter such as 01 or 10. 18 This is shown as follows: (a) If Ku>Ko,t then (b) If <K0, then 7.4 Kolmogorov complexity For instance, n = 11, or 1011 in binary, is encoded as = 1100111101. This is not a minimal-length code (as compression algorithms exist), but it surely defines n. We see that this code length is2logn+2=2logl(x)+2.The basic program that describes X and that can tell the TM to halt after outputting n bits is the same as that which prints x bit by bit (90), but with an additional instruction giving the value of N. Based on Eq. (7.14) and the above result, the length of such a program is, therefore, |qo(x)| = K[x|1(x)] + C + 2 log -210gl(x) + c for sufficiently long sequences. But as we know, if X can be described by some algorithm, the corresponding program length is such that |q(x)| < |90(x)|, meaning that the complexity of X has the upper bound (x)<Kx/l(x)]+2logl(x)+ C. (7.15) We have established that the complexity K(x) of any string x has an upper bound defined by either Eq. (7.14) or Eq. (7.15). The knowledge of an upper bound for complexity is a valuable piece of information, but it does not tell us in general how to measure it. An important and most puzzling theorem of algorithmic information theory is that complexity cannot be computed. This theorem can be stated as follows: There exists no known algorithm or formula that, given any sequence X, a Turing machine can output K(x). This leads one to conclude that the problem of determining the Kolmogorov complexity of any X is undecidable! The proof of this surprising theorem turns out to be relatively simple, as shown below. Assume that a program q exists such that a UTM can output the result U[q(x)] : K(x) for any X. We can then make up a simple program which, given x, could find at least one string having at least the same complexity as X, which we call (x) = K. Such a program r is 