 or 189 bits, plus the number of bits to define the truncation parameter, N. As the number of bits required to represent n sufficiently large is approximately log2 n, we conclude that /q/ 2 189 + log2(n). For n = 109, we have log2(n) 2 30, and the program length is approximately lql 2 189 + 30 22 220 bits, which is about 40 bits shorter than the length of the sequence X, i.e., |x| = 258 bits. The TM is capable of outputting x with a program length that is some- what shorter. As it happens, the series formula in Eq. (7.6) converges relatively slowly, in contrast to several alternative definitions. With a definition having a more rapid convergence (e.g., 22 1/n3), we may thus obtain the condition qq << |x|, illustrating that the algorithmic definition must rapidly pay off for strings with relatively large sizes. It is quite a remarkable feature that long random sequences from transcenden- numbers, such as IT, e, log 2, V2, , may be SO defined in only a few bits of TM instructions, which conveys a flavor of the elegance of algorithmic information theory. Example 7.8 Consider the following string of 150 decimal symbols: x = 4390646281 3640989838 1872779754 1099387485 5579862843 0145920705 9431329445 6125451990 7325732423 7580094766 7581012661 2285404850 7226973202 5731849141 4938800048. As in the previous example, the above string has no recognizable pattern, but it is closer to a truly random sequence (the frequencies corresponding to the 0, 1, 2, 9 symbols being 16, 13, 16, 13, 19, 15, 10, 15, 17, 16, respectively, which is close to 150/10). The string actually corresponds to a sampling of the decimal expansion of V2, starting from its millionth decimal.¹6 While we observe that the sequence is nearly random, we know, because of its finite size, that it is computable, no matter how complex the algorithm. Therefore, there must exist a TM program that outputs X, given the information that x 15 For instance, See also: http://mathworld.wolfram.com/PiFormulas.html,www.geom.uiuc.edu/~huberty/math5337/ groupe/expresspi.htm