So Kolmogorov Complexity depends on the language, but the difference between complexity in any two languages differs by at most a constant (what ever the size of an interpreter from one to the other is).
This seems to mean that the complexity ordering of different hypothesis can be rearranged by switching languages, but “only so much”. So
K1(h0)<K1(h1)<K1(h2)<K1(h3)
and
K2(h3)<K2(h2)<K2(h1)<K2(h0)
are both totally possible, as long as |K1(hi)−K2(hi)|≤c
I see how if you care about orders of magnitude, the description language probably doesn’t matter. But if you ever had to make a decision where it mattered if the complexity was 1,000,000 vs 1,000,001 then language does matter.
Where is KC actually used, and in those contexts how sensitive are results to small reordering like the one I presented?
Yeah. I guess the only place I can remember seeing it referenced in actions was with regard to assigning priors for solomonoff induction. So I wonder if it changes anything there (though solomonoff is already pretty abstracted away from other things, so it might not make sense to do a sensitivity analysis)
So Kolmogorov Complexity depends on the language, but the difference between complexity in any two languages differs by at most a constant (what ever the size of an interpreter from one to the other is).
This seems to mean that the complexity ordering of different hypothesis can be rearranged by switching languages, but “only so much”. So
K1(h0)<K1(h1)<K1(h2)<K1(h3)
and
K2(h3)<K2(h2)<K2(h1)<K2(h0)
are both totally possible, as long as |K1(hi)−K2(hi)|≤c
I see how if you care about orders of magnitude, the description language probably doesn’t matter. But if you ever had to make a decision where it mattered if the complexity was 1,000,000 vs 1,000,001 then language does matter.
Where is KC actually used, and in those contexts how sensitive are results to small reordering like the one I presented?
I am not an expert, but my guess is that KC is only used in abstract proofs, where these details do not matter. Things like:
KC in not computable
there is a constant “c” such that KC of any message is smaller than its length plus c
Etc.
Yeah. I guess the only place I can remember seeing it referenced in actions was with regard to assigning priors for solomonoff induction. So I wonder if it changes anything there (though solomonoff is already pretty abstracted away from other things, so it might not make sense to do a sensitivity analysis)