Yes, I fully agree with all of this except one point, and with that one point I only want to add a small qualification.
Sometimes someone wants to come up with a crisp definition of a concept for which I suspect no such definition to exist. I usually find that I have little to say and can only wait for them to try to actually provide such a definition. And sometimes I’m surprised by what people can come up with.
The quibble I want to make here is that if we somehow knew that the Kolmogorov complexity of the given concept was at least X (and if that was even a sensible thing to say), and somebody was trying to come up with a definition with K-complexity <<X, then we could safely say that this has no chance of working. But then in reality, we do not know anything like this, so the best we can do (as I try to do with this post) is to say “this concept seems kinda complicated, so perhaps we shouldn’t be too surprised if crisp definitions end up not working”.
I mean, translated to algorithmic description land, my claim was: It’s often difficult to prove a negative and I think the non-existence of a short algorithm to compute a given object is no exception to this rule. Sometimes someone wants to come up with a simple algorithm for a concept for which I suspect no such algorithm to exist. I usually find that I have little to say and can only wait for them to try to actually provide such an algorithm.
So, I think my comment already contained your proposed caveat. (“The concept has K complexity at least X” is equivalent to “There’s no algorithm of length <X that computes the concept.”)
Of course, I do not doubt that it’s in principle possible to know (with high confidence) that something has high description length. If I flip a coin n times and record the results, then I can be pretty sure that the resulting binary string will take at least ~n bits to describe. If I see the graph of a function and it has 10 local minima/maxima, then I can conclude that I can’t express it as a polynomial of degree <10. And so on.
Yes, I fully agree with all of this except one point, and with that one point I only want to add a small qualification.
The quibble I want to make here is that if we somehow knew that the Kolmogorov complexity of the given concept was at least X (and if that was even a sensible thing to say), and somebody was trying to come up with a definition with K-complexity <<X, then we could safely say that this has no chance of working. But then in reality, we do not know anything like this, so the best we can do (as I try to do with this post) is to say “this concept seems kinda complicated, so perhaps we shouldn’t be too surprised if crisp definitions end up not working”.
I mean, translated to algorithmic description land, my claim was: It’s often difficult to prove a negative and I think the non-existence of a short algorithm to compute a given object is no exception to this rule. Sometimes someone wants to come up with a simple algorithm for a concept for which I suspect no such algorithm to exist. I usually find that I have little to say and can only wait for them to try to actually provide such an algorithm.
So, I think my comment already contained your proposed caveat. (“The concept has K complexity at least X” is equivalent to “There’s no algorithm of length <X that computes the concept.”)
Of course, I do not doubt that it’s in principle possible to know (with high confidence) that something has high description length. If I flip a coin n times and record the results, then I can be pretty sure that the resulting binary string will take at least ~n bits to describe. If I see the graph of a function and it has 10 local minima/maxima, then I can conclude that I can’t express it as a polynomial of degree <10. And so on.