One measure of the simplicity of a proposition is the length of the shortest sentence expressing the proposition. Unfortunately, this measure is badly dependent on the choice of language. Normally, we think of the proposed law of nature
One common move is to employ theorems to the effect that given some assumptions, measures of simplicity using different languages are going to be asymptotically equivalent. These theorems look roughly like this: if cL is the measure of complexity with respect to language L, then cL(pn)/cM(pn) converges to 1 whenever pn is a sequence of propositions (or bit-strings or situations) such that either the numerator or the denominator goes to infinity. I.e., for sufficiently complex propositions, it doesn't matter which language we choose.
Unfortunately, one of the places we want to engage in simplicity reasoning in is with respect to choosing between different candidates for laws of nature. But it may very well turn out that the fundamental laws of physics—and maybe even a number of non-fundamental laws—are sufficiently simple that theorems about asymptotic behavior of complexity measures are of no help at all, since these theorems only tell us that for sufficiently complex cases the choice of language doesn't matter.