two complexities can be related. Since U is universal, by definition it has the capability of simulating the behavior of O. Therefore, there must exist a program so, independent of x, which we can input to U to instruct U how to simulate O. The U tape can thus be loaded with the program so, followed by the program 90, SO that we obtain the "simulation" output U[soqo(x)] = U[9(x)] = X. The length of the simulation program qu is simply which we can write where co is a positive constant. The associated complexity is given by (7.8) In the above, I have introduced the property minu |qu(x)| mino qu(x)|, which reflects the fact that the program qu includes the additional features of the O machine simulation that qu(x) does not have. So its minimum length in O is expected to be somewhat greater than the minimum length of qu in U. The above results thus establish the inequality: Ku(x)<<Ko(x)+ (7.9) which shows that the minimum complexity is obtained from the universal machine U. The result in Eq. (7.9) applies to all machines O different from U (otherwise, equality stands, along with co = 0). But what if O was also a universal machine? The result in Eq. (7.9) still applies since there are an infinite number of possible universal machines other than U. Then let us use O to simulate each U in turn. The same reasoning as above leads to the inequality Ko(x)<Ku(x)+cu, (7.10) where CU is a positive constant independent of X. From Eqs. (7.9) and (7.10) it is seen that the case Ku = Ko implies co = cu = 0, meaning that U and O are identical machines. Assume, in the general case, that KU # Ko. This condition also implies co # CU sup(co,cu) > 0. Combining Eqs. (7.9) and (7.10) and omitting the variable X for simplicity, yields: o>Ku-Koz-cu, (7.11) Algorithmic entropy and Kolmogorov complexity which gives a final condition on the absolute complexity difference, 18 0<Ku-Kol<sup(co,cu)=c, (7.12) with sup(co, > 0. Since KU, Ko, co, CU are program description lengths, their minimum value is unity (one bit), SO the double inequality 1</K