Your definition relies on the notion of probability though. So I'm not sure why you seemingly view Knuth's work as more fundamental than Kolmogorov's, etc.
What's the sketch of the trick? I can define randomness by appealing to some of the same basic theory used to develop probability, but it's not really independent despite looking that way from the outside. Does Knuth do this uniquely?