ting time. To define the above sequence, the only alternative for the TM is to describe it symbol by symbol, or bit by bit. By definition, a truly random sequence of 150 bits should have a descriptive complexity of, at the very least, 150 bits. It represents the minimal length of a TM program capable of outputting this sequence. The lesson learnt from these examples is that a complexity K(x) can be associated to any symbol string X, which is defined as the minimum program length for a universal Turing machine to output it. What happens if one uses a nonuniversal Turing machine? The answer is that the complexity of x increases. It is possible to show this property 17 Yet, sophisticated computer algorithms may be able to reconstruct the sequence, based on the hint that it represents a shuffling of a selection of the decimals of some computable number. What we did here is similar cryptographic coding. With such a hint, cryptographic analysis can perform various "attacks" on the encrypted sequence and eventually output the original plain sequence. It is simply a matter of computation time and memory, but Turing machines are not limited in this respect. Therefore, the proposed example is not an "incomputable" string, even if it may take a maximum of 1052 2 2173 trials to output the original sequence and TM code. Consistently, cryptographists refer to the complexity of an attack problem as being of size 2n, where n is the space of possibilities to try. 7.4 Kolmogorov complexity through a relatively simple demonstration (by "simple," I mean "simple to understand," as long as the delicate reasoning is carefully followed). Call U a universal TM and O any other machine. The programs to output X are qu(x) and 90(x), respectively, which yields the outputs U[qu(x)] = x and O[qo(x)] = X. The complexity of X is, thus, dependent on which machine is used. By definition, we have Ku(x) = minu |qu(x)| and Ko(x) = mino |qo(x)|, where the minima minu, O correspond to the two different machine types. Now comes the argument whereby the 