This post is correct, and the point is important for people who want to use algorithmic information theory.
But, as many commenters noted, this point is well understood among algorithmic information theorists. I was taught this as a basic point in my algorithmic information theory class in university (which tbc was taught by one of the top algorithmic information theorists, so it’s possible that it’s missed in other treatments).
I’m slightly frustrated that Nate didn’t realize that this point is unoriginal. His post seems to take this as an example of a case where a field is using a confused concept which can be identified by careful thought from an outsider. I think that outsiders sometimes have useful ideas that insiders are missing. But in this case, what was actually happening is that Nate just didn’t understand how insiders think about this, and had recovered from that by noticing his mistake directly himself (which is cool), rather than by realizing that he’d misunderstood the insiders.
I’d be annoyed if LWers took this as an example of doing novel intellectual work and improving a field, rather than the fact that sometimes you rederive well-known facts.
I see the main contribution/idea of this post as being: whenever you make a choice of basis/sorting-algorithm/etc, you incur no “true complexity” cost if any such choice would do.
I would guess that this is not already in the water supply, but I haven’t had the required exposure to the field to know one way or other. Is this more specific point also unoriginal in your view?
I think this point is obvious, but I don’t really remember what points were obvious when I took algorithmic info theory (with one of the people who is most likely to have thought of this point) vs what points I’ve learned since then (including spending a reasonable amount of time talking to Soares about this kind of thing).
This post is correct, and the point is important for people who want to use algorithmic information theory.
But, as many commenters noted, this point is well understood among algorithmic information theorists. I was taught this as a basic point in my algorithmic information theory class in university (which tbc was taught by one of the top algorithmic information theorists, so it’s possible that it’s missed in other treatments).
I’m slightly frustrated that Nate didn’t realize that this point is unoriginal. His post seems to take this as an example of a case where a field is using a confused concept which can be identified by careful thought from an outsider. I think that outsiders sometimes have useful ideas that insiders are missing. But in this case, what was actually happening is that Nate just didn’t understand how insiders think about this, and had recovered from that by noticing his mistake directly himself (which is cool), rather than by realizing that he’d misunderstood the insiders.
I’d be annoyed if LWers took this as an example of doing novel intellectual work and improving a field, rather than the fact that sometimes you rederive well-known facts.
I see the main contribution/idea of this post as being: whenever you make a choice of basis/sorting-algorithm/etc, you incur no “true complexity” cost if any such choice would do.
I would guess that this is not already in the water supply, but I haven’t had the required exposure to the field to know one way or other. Is this more specific point also unoriginal in your view?
I think this point is obvious, but I don’t really remember what points were obvious when I took algorithmic info theory (with one of the people who is most likely to have thought of this point) vs what points I’ve learned since then (including spending a reasonable amount of time talking to Soares about this kind of thing).