Publication

Computer Journal

Paper

# 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.