e the delimiter ";") according to either of the following: K(x;y)=K(x)+K(y)-K(x,y) K(x;y) (7.28) K(x;y)=K(y)-K(yx)+ where c' is a nonnegative constant. In Eq. (7.28), the last two definitions stem from the first one and the properties in Eqs. (7.26) and (7.27). The above results represent various relations of algorithmic complexity between two strings x, y. We immediately note that such relations bear a striking resemblance with that concerning the joint or conditional entropies and mutual information of two random- event sources X, Y according to classical IT. 22 See: G. J. Chaitin, A theory of program size formally identical to information theory. J ACM, 22 (1975), 329- 40, www.cs.auckland.ac.nz/CDMTCS/chaitin/acm75.pdf. See also: G.J. Chaitin, Algorithmic information theory. IBM J. Res. Dev., 21 (1977), 350-9, 496,www.cs.auckland.ac.nz/CDMTCS/chaitin/ibm.pdf From the first definition in Eq. (7.26) we obtain K(y/x) > K(x) - K(x,y) - c, therefore, there exists a constant c for which K(y)x)=K(x)-1 K(x,y) ' c'. 7.5 Kolmogorov complexity VS. Shannon's entropy Indeed, to recall from Chapter 5, the conditional and joint entropies are related through H(X|Y)=H(X,Y)-H(Y) (7.29) H(Y|X)=H(X,Y)-H(X), (7.30) which are definitions similar to those in Eqs. (7.26) and (7.27) for the conditional complexity. From Chapter 5, we also have, for the mutual information, H(x;y)=H(X)+H(Y)-H(X, H(x;y)=H(X)-H(XY) (7.31) H(x;y)=H(Y)-H(Y|X), which are definitions similar to that in Eq. (7.28) for the mutual complexity. It is quite remarkable that the chaining relations of conditional or joint complexities and conditional or joint entropies should be SO similar (except in algorithmic IT for the finite constant c', which is nonzero in the general case), given the conceptual differences between Kolmogorov complexity and Shannon entropy! As a matter of fact, such a resemblance between algorithmic and classical IT is not at all fortuitous. As stated at the beginning of this chapter, complexity and entropy are approximately equal when it comes t