I was referring to measures of _complexity_, variously and ill-defined, which may or may not have anything to do with KC. FI and VC-dim are, indeed, not examples of things closely related to KC, but they are useful measures of complexity nonetheless: I was answering the question as to more useful complexity measures, not as if they had to be strictly related to KC. If you had the idea that I was representing that Vapnik was poking about with KC when he was thinking about VC-dimension, I regret the misunderstanding.

But of course, they can be related to KC, because anything you say about anything computable can be related to KC: it is exactly saying, "is this complexity measure related to Turing machines?" - the answer had better be yes, unless you like writing fiction about complexity. But that "yes" is nearly always a vacuous "yes", a Turing tarpit.

Like in other places, if there was really a good definition of complexity, people would have standardized. Of the ones listed in Lloyd's note, the ones that you would expect a normal programmer to know are Shannon information and computational complexity, which are outrageously useful: Fisher information is sometimes used in neuroscience and VC dimension is used in ML, of course both as vague measures of complexity which are nice because they are computable.

There is, of course, a lot of charlatanry in the general measurement of complexity, and this is a thing not under dispute.