I haven’t seen conditional K complexity defined that way before, is there a textbook you’re getting it from? I’m not sure I’d want to drop the interpretation of conditional complexity as the length of a program, since that fits nicely with the latent string model definition, but maybe it’s a good idea anyway.
It’s not a textbook definition but it is based on Chaitin, G. J. (1975). “A Theory of Program Size Formally Identical to Information Theory.” (link)
Here’s the idea:
You have , and then you just define so the chain rule holds by construction and .
You don’t have to interpret as program receiving , though, if you treat it just as arithmetic on K complexities. It’s a bit of a stupid thing, but if I understand correctly, you can avoid any optimality assumption and keep the program-length interpretation. Because of this asymmetry:
If we start with the latent string model assumptions you already have, then you can work in for and then you just have to go the other way and pay once at the very end.
Where in the paper does Chaitin use that definition?
I think there’s some sense in which the optimality assumption will be implicit if we do it like that, but I do like the idea of not stacking up a log for every merge.
I didn’t mean to imply that it was in the paper as I have it, that’s why I said based on instead of from, sorry if that was confusing. It’s a presentational thing and it’s fine to just use instead (although I think a bit less clean).
I don’t see how there’s an implicit optimality assumption unless you’re trying to read quantities at every step in the proof as a program length. I agree that there’s something aesthetically worse about a proof that routes through something less nicely interpretable.
I haven’t seen conditional K complexity defined that way before, is there a textbook you’re getting it from? I’m not sure I’d want to drop the interpretation of conditional complexity as the length of a program, since that fits nicely with the latent string model definition, but maybe it’s a good idea anyway.
It’s not a textbook definition but it is based on Chaitin, G. J. (1975). “A Theory of Program Size Formally Identical to Information Theory.” (link)
Here’s the idea:
You have
You don’t have to interpret
If we start with the latent string model assumptions you already have, then you can work in
Where in the paper does Chaitin use that definition?
I think there’s some sense in which the optimality assumption will be implicit if we do it like that, but I do like the idea of not stacking up a log for every merge.
I didn’t mean to imply that it was in the paper as I have it, that’s why I said based on instead of from, sorry if that was confusing. It’s a presentational thing and it’s fine to just use
I don’t see how there’s an implicit optimality assumption unless you’re trying to read quantities at every step in the proof as a program length. I agree that there’s something aesthetically worse about a proof that routes through something less nicely interpretable.