For the purposes of complexity comparisons the prefix should be held constant across the algorithms. You should always be comparing algorithms in the same language.
Oh, that seems sensible. It makes the problem of choosing the language even more acute though, since now we can ignore the description length of the compiler itself, meaning that even crazy languages (such as the language which outputs Encyclopedia Brittanica with a single instruction) are in contention. The point of requiring the language to be encoded in the prefix, and its length added to the description length, is to prevent us from “cheating” in this way.
I had always assumed that it was necessary to allow the prefix to vary. Clearly “abcabcabc” and “aaabbbccc” require different prefixes to express them as succinctly as possible. In principle there’s no clear distinction between a prefix which encodes an entire new language and a prefix which just sets up a function to take advantage of the regularities of the string.
In principle there’s no clear distinction between a prefix which encodes an entire new language and a prefix which just sets up a function to take advantage of the regularities of the string.
Yes, and this is important to see. The split between content and context can be made anywhere, but the meaning of the content changes depending on where the split is made.
If you allow the prefix to change then you are considering string lengths in terms of the base language. This language can bias the result in relation to the problem domain that you are actually interested in.
For example if I want to compare the complexity of 3sat expressions, then I shouldn’t be considering algorithms in domains that support multiplication.
Oh, that seems sensible. It makes the problem of choosing the language even more acute though, since now we can ignore the description length of the compiler itself, meaning that even crazy languages (such as the language which outputs Encyclopedia Brittanica with a single instruction) are in contention. The point of requiring the language to be encoded in the prefix, and its length added to the description length, is to prevent us from “cheating” in this way.
I had always assumed that it was necessary to allow the prefix to vary. Clearly “abcabcabc” and “aaabbbccc” require different prefixes to express them as succinctly as possible. In principle there’s no clear distinction between a prefix which encodes an entire new language and a prefix which just sets up a function to take advantage of the regularities of the string.
Yes, and this is important to see. The split between content and context can be made anywhere, but the meaning of the content changes depending on where the split is made.
If you allow the prefix to change then you are considering string lengths in terms of the base language. This language can bias the result in relation to the problem domain that you are actually interested in.
As I said above: