Discussion of paper `Minimum message length and Kolmogorov complexity' by C. S. Wallace and D. L. Dowe

Abstract

The principle of minimum message length (MML) within the theory of algorithmic complexity is discussed. The MML principle is stated as: minqq{-log P(x|y)-log Q(y)}, where Q(y) is a prior probability for hypothesis y, -log Q(y) is the ideal Shannon code length for it, and -log P(x|y) the same for the data x given the hypothesis y. If in the conditional Kolmogorov complexity K(x|y) of a string x, given another string y, the latter string is interpreted as representing a hypothesis, the sum K (x|y)+K (y) could be taken as the shortest code length for the pair x, y by analogy with the MML principle.