y is that x and y are algorithmically independent, i.e., there is no algorithm q that is capable of computing both x and y. Let qx and qy (qx # qy) be the two programs describing x and y, respectively, from the same universal Turing machine U (i.e., U[qx] = X, U[qy]=y). = We can then chain the two programs to form qxy = qxqy, a program that computes x then y. There is no need for any additional instruction to the machine. Therefore, the program length is simply |9xyl = 19x1+1qyl. The minimal length of such a program is: (7.25) Algorithmic entropy and Kolmogorov complexity which shows that if two strings are algorithmically independent their joint complexity K(x,y) is given by the sum of their individual complexities. It is clear that K(x, y) = K(y,x). What if x and y are not algorithmically independent? This means that the computation of x provides some clue as to the computation of y. A program calculating y could be = qxqy|x. The machine U first computes x then uses the program qylx to compute y. Next, we shall define the conditional complexity K(y|9x), which represents the minimal size of a program describing y given the program describing X. It is also noted K(y/x*), with X* = qx, or, for simplicity, K(ylx). This last notation should be used with the awareness that |x is a condition on the program qx, not on the string X. The issue of finding the minimal size of ,=qxqy/x is far from trivial. Chaitin showed22 that K(x,y)K(x)+K(yx)+c (7.26) K(yx)=K(x,y)-K(x)+c where C represents a small overhead constant, which is one bit for sufficiently long strings. The second inequality stems from the first, with c being a nonnegative constant.²3 Since the joint complexity K(x, y) is symmetrical in the arguments X, y, we also have K(xly)=K(x,y)-K(y)+c. (7.27) If x and y are algorithmically independent, it is clear that qylx =qy (there is no clue from x to compute y), or equivalently K(y/x) K(y), and likewise, K(x|y) K(x). In this case, K(x, y) = K(x) + K(y) + c' We can now define the mutual complexity K(x;y) of X and y (not