Input K, For = 1 to infinity, Define all strings S of length n, If K(s) > K print S then halt, Continue. This program has a length + log I(K) + c. Since the program length grows as the logarithm of K, there exists a value K for which |r(K) < K. The program eventually outputs a string S of complexity K(s) > K>r, which is strictly greater than the program size! By definition, the complexity (s) of S is its minimum descriptive length. By definition, however, there is no TM program that can output S with a length shorter that K(s). Therefore, the hypothetical program q, which computes K(x) given X, simply cannot exist. Complexity cannot be computed by Turing machines (or, for that matter, by any computing machine). 19 As adapted from http://en.wikipedia.org/wiki/Kolmogorov_complexity. Algorithmic entropy and Kolmogorov complexity K - 1 1,0 00, 01, 10, 1010111 Figure 7.3 Enumeration of bit strings of size k = 0 tok = K - 1. While complexity cannot be computed, we can show that it is at least possible to achieve the following: (a) Given a complexity K, to tell how many strings x have a complexity less than K, i.e., satisfying K(x) < K; (b) For a string of given length n, to define the upper bound of its complexity, namely, to find an analytical formula for the upper bound of K[x|1(x)] in Eq. (7.15). To prove the first statement, (a), is a matter of finding how many strings X have a complexity below a given value K, i.e., satisfying K(x) < K. This can be proven by the following enumeration argument. Figure 7.3 shows the count of all possible binary strings of length k, from k = 0 (empty string) to k = K - 1. The sum of all possibilities illustrated in the figure yields (7.16) Each of these possible strings represents a TM program, to which a unique output X corresponds. There are fewer than 2K programs smaller than K, therefore there exists fewer than 2K strings of complexity < K. The statement in (b) can be proven as follows. Given any binary string x of length n, we must find the minimal-length program q that outputs 