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


are both totally possible, as long as

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?

2Viliam7moI 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)

Hazard's Shortform Feed

by Hazard 1 min read4th Feb 2018219 comments

In light of reading through Raemon's shortform feed, I'm making my own. Here will be smaller ideas that are on my mind.