l, http://en.wikipedia.org/wiki/Pi. 16 See expansion of 2 to 1 000 000 decimals in http://antwrp.gsfc.nasa.gov/htmltest/gifcity/sqrt2.1mil. Algorithmic entropy and Kolmogorov complexity represents the decimals of 2 from n = 1000000 to 1000 149. It is, thus, possible to shrink the string information to less than the string's bit length, or using a four-bit code for decimals, to less than 4* (150 + log2 = 680 bits. This number can be viewed as representing an upper bound for the minimum program length required to output X. Example 7.9 Consider the following 150-decimal string: x =1406859655 44593257548112159013 60780686628894754577 4091431997 5387666328 23134910923281754384 68093796872005607612 0145807590 2895743612 9022633078 1424279313. This string is very close to a purely random sequence. It was generated from the previous example's sequence after performing two operations: (a), replacing, at random, symbols appearing more often by symbols appearing less often, SO that they all appear exactly 15 times in the sequence; and (b), several successive random shufflings of blocks of symbols of decreasing size. Just considering the second operation, the number of possible random rearrangements is calculated to be n = 150!/(10!)¹0, which, from Stirling's formula, yields n 120.2 22 1052.2 It would take, therefore, up to some 1052 trials for a TM to find the right computing parameters to reproduce the above string, short of knowing the shuffling algorithm that was used.¹ To imagine the size of 1052, assume that a TM is capable of computing at the amazing speed of 1 billion trials per second. It is easy to find that the computation time is about 1035 years, or 1026 billion years! Any hint of the operations (a) and (b) could reduce the computing time to the same order as in the previous example. But since the author has chosen to destroy irremediably the records of his (b) operations, one may consider that x is definitely incomputable and taken as a random sequence for which no algorithm can be found within reasonable compu