. As encoded into ASCII, which takes seven bits per alphanumeric character, the program length is /q/ = 19 X 7 = 133 bits, as opposed to 7000 bits if the sequence was crudely encoded "as is." But this is not the shortest possible program. For instance, we could also define it under the more concise form = A = 1, B = 0, R 10 X 500, where R stands for "repeat" and X for "as many times as." The length of q(x) is now 15 characters or 15 x 7 = 105 bits. If this program represent the absolutely minimal way to describe such a sequence, the sequence complexity is K(x) = 105 bits. Example 7.7 Consider the following binary sequence: =11.001001000011111101101010 1000100010000101 10100011 00001000 11010 01100010011 00011001 10001010 00101110 00000011 01110000011100110100010 010100100 00001001 00111000 00100010 00101001 100111116 00110001 11010000 00001000 00101110 11111010 10011000 11101100 01001110 01101100 10001001, which is made of 258 bits, i.e., 149 Os and 109 1s, plus a radix point (the equivalent of the decimal point in the binary system). Such a sequence has no recognizable pattern and is close to random. But, as it happens, it corresponds to the exact binary expansion of the number IT = 3.141592653589 up to 256 digital places¹4 (or eight decimal places). Since there are various algorithms to calculate IT up to any arbitrary precision, one could replace the above string by the shortest such algorithm. For instance, one definition of IT is given by the series (7.6) 14 See binary expansion of IT over 30 000 digits in www.befria.nu/elias/pi/binpi.html. 7.4 Kolmogorov complexity 00. It can be shown that the error IT - Tn is of the order of 1/(2n), SO it takes about one billion terms (n = 10°) to achieve an accuracy of 1/(2 X 109) = 5 X 10-10. which is better than eight decimal places. Based on the above formula, the TM algorithm could then be packaged under the form (operand symbols being straightforward to interpret): q(x) = S[k, 1, n; P(-1;k+1)/(2xk-1)], (7.7) which, in this general form, takes only 27 ASCII characters