Heh, I’m still skimming enough to catch this, but definitely not evaluating arguments.
I’m definitely still open to both changing my mind about the best use of terms and also updating the terminology in the sequence (although I suspect that will be quite a non-trivial amount of modified prose). And I think it’s best if I don’t actually think about it until after I publish another post.
I’d also be much more inclined to think harder about this discussion if there were more than two people involved.
My main goal here has always been “clearly explain the existing content so that people can understand it”, which is very different from “propose a unification of the whole field” (it’s just that “unification” is my native method of understanding).
Cool cool. A summary of the claims that feel most important to me (for your convenience, and b/​c I’m having fun):
K-complexity /​ “algorithmic entropy” is a bad concept that doesn’t cleanly relate to physics!entropy or info!entropy.
In particular, the K-complexity of a state s is just the length of the shortest code for s, and this is bad because when s has multiple codes it should count as “simpler”. (A state with five 3-bit codes is simpler than a state with one 2-bit code.) (Which is why symmetry makes a concept simpler despite not making its code shorter.)
If we correct our notion of “complexity” to take multiple codes into account, then we find that complexity of a state s (with respect to a coding scheme C) is just the info!cross-entropy H(s,C). Yay!
Separately, some gripes:
the algorithmic information theory concept is knuckleheaded, and only approximates info!entropy if you squint really hard, and I’m annoyed about it
I suspect that a bunch of the annoying theorems in algorithmic information theory are annoying precisely because of all the squinting you have to do to pretend that K-complexity was a good idea
And some pedagogical notes:
I’m all for descriptive accounts of who uses “entropy” for what, but it’s kinda a subtle situation because:
info!entropy is a very general concept,
physics!entropy is an interesting special case of that concept (in the case where the state is a particular breed of physical macrostate),
algo!entropy is a derpy mistake that’s sniffing glue in the corner,
algo!entropy is sitting right next to a heretofore unnamed concept that is another interesting special case of info!(cross-)entropy (in the case where the code is universal).
(oh and there’s a bonus subtlety that if you port algo!entropy to a situation where the coding schema has at most one code per state—which is emphatically not the case in algorithmic information theory—then in that limited case it agrees with info!cross-entropy. Which means that the derpiness of algo!entropy is just barely not relevant to this particular post.)
So, uh, good luck.
And separately, the key points about notation (while I’m summarizing, acknowledging that the notation might not to change in your coming posts):
The corrected notion of the “complexity” of a state s given a coding scheme C is H(s,C)
It’s confusing to call this the “entropy” of s, because that sounds like H(s), which by long-established convenient convention means H(s,s).
An elegant solution is to just call this the “(C-)complexity” of s instead.
This highlights a cool reciprocal relationship between (cross-)entropy and complexity, where the s-entropy of C is the same as the C-complexity of s. This can perhaps be mined for intuition.
Convergence! 🎉🎉. Thanks for the discussion; I think we wound up somewhere cooler than I would have gotten to on my own.
Now we just need to convince Alex :-p. Alex, are you still reading? I’m curious for your takes on our glorious proposal.
Heh, I’m still skimming enough to catch this, but definitely not evaluating arguments.
I’m definitely still open to both changing my mind about the best use of terms and also updating the terminology in the sequence (although I suspect that will be quite a non-trivial amount of modified prose). And I think it’s best if I don’t actually think about it until after I publish another post.
I’d also be much more inclined to think harder about this discussion if there were more than two people involved.
My main goal here has always been “clearly explain the existing content so that people can understand it”, which is very different from “propose a unification of the whole field” (it’s just that “unification” is my native method of understanding).
Cool cool. A summary of the claims that feel most important to me (for your convenience, and b/​c I’m having fun):
K-complexity /​ “algorithmic entropy” is a bad concept that doesn’t cleanly relate to physics!entropy or info!entropy.
In particular, the K-complexity of a state s is just the length of the shortest code for s, and this is bad because when s has multiple codes it should count as “simpler”. (A state with five 3-bit codes is simpler than a state with one 2-bit code.) (Which is why symmetry makes a concept simpler despite not making its code shorter.)
If we correct our notion of “complexity” to take multiple codes into account, then we find that complexity of a state s (with respect to a coding scheme C) is just the info!cross-entropy H(s,C). Yay!
Separately, some gripes:
the algorithmic information theory concept is knuckleheaded, and only approximates info!entropy if you squint really hard, and I’m annoyed about it
I suspect that a bunch of the annoying theorems in algorithmic information theory are annoying precisely because of all the squinting you have to do to pretend that K-complexity was a good idea
And some pedagogical notes:
I’m all for descriptive accounts of who uses “entropy” for what, but it’s kinda a subtle situation because:
info!entropy is a very general concept,
physics!entropy is an interesting special case of that concept (in the case where the state is a particular breed of physical macrostate),
algo!entropy is a derpy mistake that’s sniffing glue in the corner,
algo!entropy is sitting right next to a heretofore unnamed concept that is another interesting special case of info!(cross-)entropy (in the case where the code is universal).
(oh and there’s a bonus subtlety that if you port algo!entropy to a situation where the coding schema has at most one code per state—which is emphatically not the case in algorithmic information theory—then in that limited case it agrees with info!cross-entropy. Which means that the derpiness of algo!entropy is just barely not relevant to this particular post.)
So, uh, good luck.
And separately, the key points about notation (while I’m summarizing, acknowledging that the notation might not to change in your coming posts):
The corrected notion of the “complexity” of a state s given a coding scheme C is H(s,C)
It’s confusing to call this the “entropy” of s, because that sounds like H(s), which by long-established convenient convention means H(s,s).
An elegant solution is to just call this the “(C-)complexity” of s instead.
This highlights a cool reciprocal relationship between (cross-)entropy and complexity, where the s-entropy of C is the same as the C-complexity of s. This can perhaps be mined for intuition.
Endorsed.