Since simplicity is such a core heuristic of rationality, having a correct conceptualization of complexity is important.
The usual definition of complexity used on LW (and elsewhere) is Kolmogorov Complexity, which the length of its shortest code. Nate suggests a compelling idea—that another way to be simple is to have many different codes. For example, a state with five 3-bit codes is simpler than a state with one 2-bit code.
Nate justifies that with a bunch of math, and some physics, which I don’t understand well enough to comment on.
A bunch of people who do understand the math well enough basically agreed with Nate, but commented that Soares’s Complexity differes from Kolmogorov Complexity by at most a constant. After some discussion Nate was convinced and edited a note saying that into the post, but then @intersticesaid that this only applies to finite strings while Nate is talking about semimeasures on infinite sequences, which do have a non-constant gap.
So, though I don’t feel qualified to say it, my understanding is that this is indeed a superior measure of complexity and, at least on LW, should replace Kolmogorov Complexity as the default meaning of complexity.
And since improving our understanding of complexity seems quite important, I’m giving this post 4 points.
Admittedly, as much as I do think that Kolmogorov Complexity is worse than Alt-Complexity, I do think that it has one particular use case that Alt-complexity does not have:
It correctly handles the halting oracle case, and generally handles the ideal/infinite cases quite a lot better than Alt-complexity/Solomonoff log-probability, and this is a case where alt-complexity does quite a lot worse.
Alt-complexity intelligence is very much a theory of the finite, and also a restrictive finite case at that, and doesn’t attempt to deal with the infinite case, or cases where it’s still finite but some weird feature of the environment allows halting oracles and I think they’re right, at least for the foreseeable future to ignore this case, but Kolmogorov Complexity definitely deals with the infinite/ideal cases way better than Alt-complexity when it comes to intelligence.
Since simplicity is such a core heuristic of rationality, having a correct conceptualization of complexity is important.
The usual definition of complexity used on LW (and elsewhere) is Kolmogorov Complexity, which the length of its shortest code. Nate suggests a compelling idea—that another way to be simple is to have many different codes. For example, a state with five 3-bit codes is simpler than a state with one 2-bit code.
Nate justifies that with a bunch of math, and some physics, which I don’t understand well enough to comment on.
A bunch of people who do understand the math well enough basically agreed with Nate, but commented that Soares’s Complexity differes from Kolmogorov Complexity by at most a constant. After some discussion Nate was convinced and edited a note saying that into the post, but then @interstice said that this only applies to finite strings while Nate is talking about semimeasures on infinite sequences, which do have a non-constant gap.
So, though I don’t feel qualified to say it, my understanding is that this is indeed a superior measure of complexity and, at least on LW, should replace Kolmogorov Complexity as the default meaning of complexity.
And since improving our understanding of complexity seems quite important, I’m giving this post 4 points.
Note that Nate’s proposal is not original; this is him rederiving and popularizing points that are known, rather than learning new ones.
Admittedly, as much as I do think that Kolmogorov Complexity is worse than Alt-Complexity, I do think that it has one particular use case that Alt-complexity does not have:
It correctly handles the halting oracle case, and generally handles the ideal/infinite cases quite a lot better than Alt-complexity/Solomonoff log-probability, and this is a case where alt-complexity does quite a lot worse.
Alt-complexity intelligence is very much a theory of the finite, and also a restrictive finite case at that, and doesn’t attempt to deal with the infinite case, or cases where it’s still finite but some weird feature of the environment allows halting oracles and I think they’re right, at least for the foreseeable future to ignore this case, but Kolmogorov Complexity definitely deals with the infinite/ideal cases way better than Alt-complexity when it comes to intelligence.
Links are below:
Alt-Complexity intelligence: https://www.lesswrong.com/posts/gHgs2e2J5azvGFatb/infra-bayesian-physicalism-a-formal-theory-of-naturalized#Evaluating_agents
Kolmogorov Complexity intelligence: https://www.lesswrong.com/posts/dPmmuaz9szk26BkmD/vanessa-kosoy-s-shortform?commentId=Tg7A7rSYQSZPASm9s#Tg7A7rSYQSZPASm9s