u-Kole (7.13) also holds. The conclusion is that it is possible to find two different universal Turing machines capable of outputting X, and the minimum difference in the complexities is at least one bit. We consider next the issue of determining the complexity of a string X with a known length 1(x). In Example 7.9, we have seen that if the string X is incomputable, but has a finite length 1(x), one can devise a halting program 90 that defines X as a mere symbol-by-symbol or bit-by-bit description. The length of such a program (or descrip- tive length) is lq(x)| = 1(x) + c, where C is a constant taking care of TM instructions, such as "print" or "stop on string delimiter #." We conclude, therefore, that the associ- ated complexity is K(x) = minu |q(x) = 1(x) + minu C = 1(x) + c' (in the following, I will use C or C' to mean any nonzero positive constants). The fact that the string length 1(x) is known a priori is an important piece of information in the definition of the program q(x). In this condition, it is sensible to call this complexity the con- ditional complexity of X, which we note K[x|1(x)]. Conditional complexity literally means The descriptive length of the program that outputs X with knowledge of the length of X. Based on the above, we have established the following property for any string of known length 1(x): (7.14) (the sign < being introduced instead of = to signify any arbitrary constant c), which provides an upper bound for conditional complexity. Assume next the case of strings whose lengths are unknown a priori but can be defined by some algorithm (or through any computable analytical or iterative formula). Thus (because there is an algorithm), there must exist a TM program q such that 1q(x)| < 1(x) + C. Since an algorithm is generally not able to tell the string length 1(x), therefore, the upper bound in Eq. (7.14) does not apply for K(x). If we want a machine to output a string of definite length 1(x) = n, the program must contain this information in the form of an instruction. A possible wa