To misuse localdeity’s example, suppose I want to build a wall with as many cubbyholes as possible, so that I can store my pigeons in them. In comparison to a blank wall, each hole makes the wall more complex, since there are more ways to arrange n+1 holes than to arrange n holes (assuming the wall can accommodate arbitrarily many holes).
Then use an encoding M2 which assigns very long codes to smooth walls. You’ll need long codes for the greebled walls, since there’s such a large number of greeblings, but you can still use even longer codes for smooth walls.
I don’t see how to do that, especially given that it’s not a matter of meeting some threshold, but rather of maximizing a value that can grow arbitrarily.
Actually, you don’t even need the ways-to-arrange argument. Suppose I want to predict/control the value of a particular nonnegative integer n (the number of cubbyholes), with monotonically increasing utility, e.g. U(n)=n. Then the encoding length E(n) of a given outcome must be longer than the code length for each greater outcome: E(n)>E(n+k). However, code lengths must be a nonnegative integer number of code symbols in length, so for any given encoding E(n) there are at most E(n) shorter code lengths, so the encoding E must fail no later than n+E(n)+1.
What if I want greebles?
To misuse localdeity’s example, suppose I want to build a wall with as many cubbyholes as possible, so that I can store my pigeons in them. In comparison to a blank wall, each hole makes the wall more complex, since there are more ways to arrange n+1 holes than to arrange n holes (assuming the wall can accommodate arbitrarily many holes).
Then use an encoding M2 which assigns very long codes to smooth walls. You’ll need long codes for the greebled walls, since there’s such a large number of greeblings, but you can still use even longer codes for smooth walls.
I don’t see how to do that, especially given that it’s not a matter of meeting some threshold, but rather of maximizing a value that can grow arbitrarily.
Actually, you don’t even need the ways-to-arrange argument. Suppose I want to predict/control the value of a particular nonnegative integer n (the number of cubbyholes), with monotonically increasing utility, e.g. U(n)=n. Then the encoding length E(n) of a given outcome must be longer than the code length for each greater outcome: E(n)>E(n+k). However, code lengths must be a nonnegative integer number of code symbols in length, so for any given encoding E(n) there are at most E(n) shorter code lengths, so the encoding E must fail no later than n+E(n)+1.
Ah, this is the same as Daniel’s question. Take a look at the answers there.